statement：https://codeforces.com/gym/104337/problem/G 。
即求 \(f(x)=\sum\limits_{i=0}^{p-2}a_ix^i\)，其中只有不超过 \(n\) 个 \(a_i\) 非 \(0\) 。
记：
\[\begin{aligned} A_{n}^{k}&=\sum_{i\equiv k\pmod{n}}a_i=\frac{1}{n}\sum_{i=0}^{n-1}f(\omega_{n}^{i})\omega_{n}^{-ik}\\ B_{n}^{k}&=A_{2n}^{k}-A_{2n}^{k+n}=\frac{1}{n}\sum_{i=0}^{n-1}f(\omega_{n}^{i}\omega_{2n})\omega_{n}^{-ik}\omega_{2n}^{-k} \end{aligned} \]假设我们对 \(0\leq k<n\) 都知道 \(A_{n}^{k}\) 。因为 \(A_{2n}^k=\frac{1}{2}(A_n^k+B_n^k),A_{2n}^{k+n}=\frac{1}{2}(A_n^k-B_n^k)\)，所以只要求所有 \(B_{n,k}\) 就可以了。将 \(B_{n}^{k}\) 的表达式拆解，应用单位根反演可以得到：
\[\begin{bmatrix} B_{n}^{0}\omega_{2n}^{0}\\ B_{n}^{1}\omega_{2n}^{1}\\ \vdots\\ B_{n}^{n-1}\omega_{2n}^{n-1} \end{bmatrix} \cdot (\omega_{n}^{ij})_{i,j} = \begin{bmatrix} f(\omega_{n}^{0}\omega_{2n})\\ f(\omega_{n}^{1}\omega_{2n})\\ \vdots\\ f(\omega_{n}^{n-1}\omega_{2n}) \end{bmatrix} \]但是有用的值其实不多：注意到 \(a_i\leq 10^5\)，因此任意集合 \(S\subseteq[0,p-2]\) 满足，若 \(\sum\limits_{i\in S}a_i=0\) 则每个 \(a_i,i\in S\) 都是 \(0\) 。于是若 \(A_{n}^k=0\) 则 \(B_{n}^k\) 必然为 \(0\) 。考虑非零位 \(\{k_0,k_1,\cdots,k_{m-1}\}\)，令 \(\alpha_{i}=\omega_{n}^{k_i},b_i=B_n^{k_i}\omega_{2n}^{k_i}\)，有：
\[\begin{bmatrix} b_0\\b_1\\\vdots\\b_{m-1} \end{bmatrix} \cdot (\alpha_{i}^{j})_{i,j} = \begin{bmatrix} f(\omega_{n}^{0}\omega_{2n})\\ f(\omega_{n}^{1}\omega_{2n})\\ \vdots\\ f(\omega_{n}^{m-1}\omega_{2n}) \end{bmatrix} \]因为只需要解方程，所以其实只要 \(m\times m\) 就够了。现在我们需要观察 \(m\) 阶方阵 \((\alpha_{i}^{j})_{i,j}\) 的性质。
令 \(M=(\alpha_{j}^{i})_{i,j}\) 为上述矩阵的转置，是范德蒙德矩阵。作用 \(aM=b\) 的意义是多点求值，反过来其逆矩阵可以写成拉格朗日插值：\((M^{-1})_{i,j}=[x^j]\prod\limits_{k\not=i}\frac{x-\alpha_{k}}{\alpha_i-\alpha_k}\) 。
此时：
\[\begin{aligned} b_i&=\sum_{j=0}^{m-1}f(\omega_{n}^{j}\omega_{2n})(M^{-1})_{j,i}\\ &=\sum_{j=0}^{m-1}f(\omega_{n}^{j}\omega_{2n})[x^j]\prod\limits_{k\not=i}\frac{x-\alpha_{k}}{\alpha_i-\alpha_k}\\ \end{aligned} \]那么只要求出 \(0\leq j< m\) 的 \(f(\omega_{n}^{j}\omega_{2n})\) 即可。而 \(A_{n}^{k}\) 的非零个数至多 \(10^3\) 个。考虑倍增到 \(p_i\) 上界，询问次数大概是 \(\sum\limits_{i=1}^{23}\min(10^3,2^{i-1})\)，是满足要求的。
我们通过设计倍增很好地解决了这个问题。其关键在于，得设计使得每轮倍增需要处理的量级，和非零总数相关。以此先设计 \(A\)，为了 \(A_n\rightarrow A_{2n}\) 设计出 \(B_n\)，联系值域找到 \(B\) 的性质，得到求解方法。
标签：Guess,end,题解,gym,bmatrix,alpha,2n,omega,sum From： https://www.cnblogs.com/qiulyqwq/p/17548625.html