考虑求\(x^n\mod p(x)\)
\(p\)是一个多项式。
发现\(p(x)=x^k-p_1x^{k-1}+...-p^kx^0\)
用归纳法证明。
假设现在取模\(x_k\)，\(x_k\)的系数是\(a_{n-k}\)
事实上这一位会向后面的\(x_{k-j}\)贡献\(p_j*a_{n-k}\)
后面某一位\(x_k\)接受的贡献事实上\(\sum_{i=1}^k[x^{k+i}](x^n\mod p(x))p_i\)
得证。
用倍增求多项式取模，多项式最高次就是答案。
这个做法理解起来更简单
原文：https://www.cnblogs.com/ctmlpfs/p/14772178.html