常系数线性齐次递推新理解

本文主要是介绍常系数线性齐次递推新理解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考虑求\(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\)
得证。
用倍增求多项式取模即可。
这个做法理解起来更简单

这篇关于常系数线性齐次递推新理解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！