statement：https://codeforces.com/gym/104337/problem/G 。
即求 \(f(x)=\sum\limits_{i=0}^{p-2}a_ix^i\)，其中只有不超过 \(n\) 个 \(a_i\) 非 \(0\) 。
记：
假设我们对 \(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}\) 的表达式拆解，应用单位根反演可以得到：
但是有用的值其实不多：注意到 \(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}\)，有：
因为只需要解方程，所以其实只要 \(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}\) 。
此时：
那么只要求出 \(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\) 的性质，得到求解方法。