多项式

由若干个单项式相加组成的代数式叫做多项式
形如：f(x)=∑i=0naixi" role="presentation">f(x)=∑ni=0aixi$f(x)=\sum _{i=0}^n{a}_i{x}^i$，
deg⁡ f(x)" role="presentation">deg f(x)$\mathrm{deg}f(x)$称为f" role="presentation">f$f$的度，是f(x)" role="presentation">f(x)$f(x)$最高次项的次数。

生成函数

形如∑i=0∞aixi" role="presentation">∑∞i=0aixi$\sum _{i=0}^{\mathrm{\infty }}{a}_i{x}^i$
生成函数又称母函数，往往和多项式算法联系起来起到优化转移的作用

多项式算法

加减法

多项式加减法比较简单
若f(x)=∑i=0naixi" role="presentation">f(x)=∑ni=0aixi$f(x)=\sum _{i=0}^n{a}_i{x}^i$，g(x)=∑i=0nbixi" role="presentation">g(x)=∑ni=0bixi$g(x)=\sum _{i=0}^n{b}_i{x}^i$ 则(f±g)(x)=∑i=0n(ai±bi)xi" role="presentation">(f±g)(x)=∑ni=0(ai±bi)xi$(f\pm g)(x)=\sum _{i=0}^n(a_i\pm b_i)x^i$ 代码实现也比较简单

---

乘法

多项式乘法是所有多项式算法的基础，也是生成函数的卷积运算 若f(x)=∑i=0naixi" role="presentation">f(x)=∑ni=0aixi$f(x)=\sum _{i=0}^n{a}_i{x}^i$，g(x)=∑i=0nbixi" role="presentation">g(x)=∑ni=0bixi$g(x)=\sum _{i=0}^n{b}_i{x}^i$ 则(f×g)(x)=∑i=02n∑j=0iaj×bi−jxi" role="presentation">(f×g)(x)=∑2ni=0∑ij=0aj×bi−jxi$(f\times g)(x)=\sum _{i=0}^{2n}\sum _{j=0}^i{a}_j\times b_{i-j}{x}^i$ 朴素的多项式乘法是O(n2)" role="presentation">O(n2)$O(n^2)$的，但FFT（快速傅里叶变换）运用复数根的特性可以在O(nlog⁡n)" role="presentation">O(nlogn)$O(n\log n)$的复杂度内实现多项式的系数表达和点值表达的转化，运用点值表达实现O(n)" role="presentation">O(n)$O(n)$的相乘，总复杂度就是O(nlog⁡n)" role="presentation">O(nlogn)$O(n\log n)$，但是因为常数过大，往往小范围会使用暴力。 inline void FFT(E *a,int r){ for(int i=0;iif(rev[i]>i) swap(a[rev[i]],a[i]); for(int i=1;i1){ E wn(cos(M_PI/i),r*sin(M_PI/i)); for(int j=0;j1)){ E w(1,0); for(int k=0;k*wn){ E x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y; a[j+k+i]=x-y; } } } if(r==-1) for(int i=0;i 运用生成函数的计数问题往往会对一个质数取模，如果这个质数可以表示成k×2n+1" role="presentation">k×2n+1$k\times 2^n+1$，其中k" role="presentation">k$k$为奇数n" role="presentation">n$n$大于多项式的度数，那么就可以用这个质数的原根代替复数根，实现多项式的系数对一个质数取模，这个算法就是NTT（快速数论变换），这种模数称为NTT模数。 inline void Pre(int n){ num=n; int g=Pow(3,(P-1)/num); w[0][0]=w[1][0]=1; for(int i=1;i0][i]=1LL*w[0][i-1]*g%P; for(int i=1;i1][i]=w[0][num-i]; } inline void NTT(int *a,int n,int r){ for(int i=1