我在做高代作业的时候走了条错路，但发现这个错路其实很有意思，所以下面的推导多半不是最简洁的推导方法。
$V$指范德蒙矩阵\(\begin{pmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1}\\ \end{pmatrix}\)，众所周知$\det{V}=\prod_{i\lt j}(x_j-x_i)$。
$A_{ij}$指\(\begin{pmatrix}x_1&x_1^2&\cdots&x_1^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n^2&\cdots&x_n^{n}\end{pmatrix}\)的第$i$行$j$列的代数余子式。
下面通过按行求和与按列求和的方式分别求$\sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}$。
按列求和
考虑求$\sum_{i=1}^{n}A_{ik}$，这相当于求将$A$的第$k$列替换成全$1$后的行列式。显然$\sum_{i=1}^{n}A_{in}=(-1)^{n-1}\det V$。下设$k\lt n$。
将第$k$列前移到第$1$列，再把第$n$列移到第$k$列剩下的缝隙，可以得到$\sum_{i=1}^{n}A_{ik}=(-1)^{k-1}(-1)^{n-(k+1)}V_{k}=(-1)^{n}V_{k+1}$，其中的$V_k$指将$V$的第$k$列替换成$(x_1^{n},x_2^n,\cdots,x_n^n)^T$的行列式。
使用Cramer法则，可以得到$V_k=\boldsymbol{x}_{k}\det V$，其中的$\boldsymbol{x}$为$V\boldsymbol{x}=(x_1^{n},x_2^n,\cdots,x_n^n)^T$的解。
考虑$V\boldsymbol{x}=(x_1^{n},x_2^n,\cdots,x_n^n)^T$这个线性方程组的意义：这是在用待定系数法寻找以全体$x_k$为根的首一多项式的系数。但显然这个多项式就是$\prod\limits_{k=1}^{n}(x-x_k)$，因此\(\boldsymbol{x}_i=-[x^{i-1}]\prod\limits_{k=1}^{n}(x-x_k)\) （\([x^k]P(x)\)表示$P(x)$的$x^k$项系数）
因此
\[\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}&=a^n(-1)^{n-1}\det V+\sum_{j=1}^{n-1}a^j\sum_{i=1}^{n}A_{ij}\\ &=a^n(-1)^{n-1}\det V+(-1)^n\sum_{i=1}^{n-1}a^iV_{i+1}\\ &=(-1)^n\det V\left(-a^n+\sum_{i=2}^{n}a^{i-1}\boldsymbol{x}_i\right)\\ &=(-1)^{n-1}\det V\left(a^n+\sum_{i=1}^{n-1}a^i[x^{i}]\prod_{k=1}^{n}(x-x_k)\right)\\ &=(-1)^{n-1}\det V\left(\sum_{i=0}^{n}a^i[x^{i}]\prod_{k=1}^{n}(x-x_k)-\prod_{k=1}^{n}(-x_k)\right)\\ &=\prod_{i\lt j}(x_j-x_i)\left(\prod_{k=1}^{n}x_k+(-1)^{n-1}\prod_{k=1}^{n}(a-x_k)\right)\\ &=\prod_{i\lt j}(x_j-x_i)\left(\prod_{k=1}^{n}x_k-\prod_{k=1}^{n}(x_k-a)\right) \end{aligned}\]按行求和
考虑$\sum\limits_{i=1}^{n}a^iA_{ki}$，可以把它写成\(\begin{vmatrix} x_1&x_1^2&\cdots&x_1^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{k-1}&x_{k-1}^2&\cdots&x_{k-1}^{n}\\ a&a^2&\cdots&a^n\\ x_{k+1}&x_{k+1}^2&\cdots&x_{k+1}^{n}\\ \vdots&\vdots&\ddots&\vdots\\ x_n&x_n^2&\cdots&x_n^{n}\\ \end{vmatrix}\)，这还是范德蒙行列式（乘上$a\prod_{i\ne k}x_i$），即
\[\begin{aligned} \sum\limits_{i=1}^{n}a^iA_{ki}&=a(-1)^{k+1}\prod_{i\ne k}x_i(x_i-a)\prod_{i\lt j;i,j\ne k}(x_j-x_i) \end{aligned}\]因此
\[\sum_{i=1}^{n}\sum_{j=1}^{n}a^jA_{ij}=a\sum_{k=1}^{n}(-1)^{k+1}\prod_{i\ne k}x_i(x_i-a)\prod_{i\lt j;i,j\ne k}(x_j-x_i)\]如果$x_k$两两不等，实际上这个变形总是正确的，因为交错多项式必有范德蒙行列式为因式
因此
\[\begin{aligned} \sum_{k=1}^{n}\frac{1}{x_k}\prod_{i\ne k}\frac{a-x_i}{x_k-x_i}&=\frac{\prod_{k=1}^{n}x_k-\prod_{k=1}^{n}(x_k-a)}{a\prod_{k=1}^{n}x_k}\\ &=\frac{1}{a}\left(1-\prod_{k=1}^{n}(1-\frac{a}{x_k})\right) \end{aligned}\]很容易验证这是一个$a$的多项式，并且在$a=x_k$时取值$\dfrac{1}{x_k}$。但肯定大家都想简化下这个推导过程。
简单的想法
想要构造一个这样的多项式，显然只需要构造一个在全部$x_k$处取值为$1$，并且没有常数项的多项式，然后除以$x$就行了；而这只需要构造一个在全部$x_k$处取值为$0$且常数项是$1$的多项式，然后用$1$减掉就行了；最后这个构造是显然的，$P(x)=\prod\limits_{k=1}^{n}(1-\frac{x}{x_k})$。
但这个结果没有太大意义，毕竟无论是求单点值还是求多点值，貌似复杂度都不会比暴力插值更优$\dots$
