写点做多项式笔记以及遇到的各种蛋疼的东西....（不懂可以Q我辣我十分愿意！

（picks博客已经成为中国多项式入门到精通的经典教程辣！详见：http://picks.logdown.com/archives

多项式乘法：

裸的fft= =复数搞搞

数论变换的多项式乘法：

对于一些要对系数取模而取的模十分鬼畜即满足存在$k$，使得$2^k | (P-1) 且 2^k > n$时那么可以用一个$P$的原根代替复数根，即用$g^{\frac{P-1}{m}}$代替fft里的单位根$\omega ^{ \frac{2 \pi i}{m} }$。其逆为$n^{-1} g^{-\frac{P-1}{m}}$。容易证明这是正确的。（可以照着算导对单位根的所需要性质然后来证明）

多项式求逆：

这个求逆指的是对一个$mod$特定次数的$x$求逆，例如求$A(x)$在模$x^n$下的逆，即求一个$B(x)$使得$A(x)B(x) \equiv 1 \pmod{x^n}$，这个用倍增的思想容易得到

$$ B_{n}(x) \equiv B_{ \left \lceil \frac{n}{2} \right \rceil } \left( 2 - A(x)B_{ \left \lceil \frac{n}{2} \right \rceil } \right) \pmod{x^n} $$

$B_{n}(x)$指的是在模$x^n$下的$A$的逆

这里一定注意在码的时候，右式得到的次数界应该大于等于$n+n$（在这里大于的部分被模掉了！）的啊...不要以为是$n+\left \lceil \frac{n}{2} \right \rceil +1$啊555，在这里wa了好多发啊QAQ

多项式除法+取模：

指的是给出$A(x), B(x)$求$A(x) = B(x)C(x) + D(x)$，其中满足$deg(A)=deg(B)+deg(C), deg(D)<deg(B)$

这里需要用点技巧orz如果能想到翻转多项式那么这题就好做了orz令$F^{R}(x)$表示将多项式$F(x)$系数前后翻转后的多项式，即$F^{R}(x) = x^{deg(F)} F(\frac{1}{x})$。那么我们将$\frac{1}{x}$先带入$A(x) = B(x)C(x) + D(x)$并乘上一个$x^{deg(A)}$最后化简能得到就能得到

$$A^R(x) \equiv B^R(x)C^R(x) \pmod{x^{deg(A)-deg(B)}}$$

取模也相应解决了

多项式开根：

指的是在模$x^n$的意义下给出$A(x)$，求$\sqrt{A(x)}$。那么能开根的条件就是$A(x)$的最低次是2的倍数且系数能被开根。

如果想到倍增这个问题也是很好解决的...最终得到

$$A \equiv \left( 2^{-1} A_{ \left \lceil \frac{n}{2} \right \rceil } + 2^{-1} A A_{ \left \lceil \frac{n}{2} \right \rceil }^{-1} \right)^2 \pmod{x^n}$$

下标的意义同求逆那里。（$A_{t}$表示$A_{t}^2 \equiv A \pmod{x^t}$

要注意的和求逆那里一样，右式次数界同样是大于等于$n+n$且求逆的时候是取模$x^n$下的逆，因为$A_{ \left \lceil \frac{n}{2} \right \rceil }^{-1}$的次数界可能为$n$。

对应的例题看picks博客辣= =

 

多项式求逆：

#include 
     
      using namespace std;typedef long long ll;const int N=130050, fN=N<<2;const ll mo=1004535809;ll G[35], nG[35];int rev[fN];ll ipow(ll a, int b) { ll x=1; for(; b; b>>=1, (a*=a)%=mo) if(b&1) (x*=a)%=mo; return x; }void fft(ll *a, int n, int f) {	for(int i=0; i
      
       >1; ++now;		ll wn=G[now]; if(f) wn=nG[now];		for(int i=0; i
       
        >1);	int len=1, bl=-1, nn=(n<<1)-1;	for(; len
        
         >1]>>1)|(((ll)i&1)<
         
          =0; --i) G[i]=G[i+1]*G[i+1]%mo, nG[i]=nG[i+1]*nG[i+1]%mo;	ni[1]=1; p[1]=1; p[0]=1;	for(int i=2; i<=n; ++i) ni[i]=((-(mo/i)*ni[mo%i])%mo+mo)%mo;	for(int i=2; i<=n; ++i) p[i]=p[i-1]*ni[i]%mo;	A[0]=1, B[0]=0;	ll last=1, C=1;	for(int i=1; i<=n; ++i) A[i]=last*p[i]%mo, B[i]=last*p[i-1]%mo, last=last*((C<<=1)%=mo)%mo;	getinv(A, nA, n+1);	for(int i=1; i
          
           >1]>>1)|(((ll)i&1)<
          
         
        
       
      
     

　　

多项式除法+取模：

#include 
     
      using namespace std;typedef long long ll;#define CC(a, b) memset(a, 0, sizeof(int)*(b))const int N=130005, fN=N<<2, BN=30, mo=1004535809, n_G=3;int G[BN], nG[BN], rev[fN];int ipow(int a, int b) { int x=1; for(; b; b>>=1, a=(ll)a*a%mo) if(b&1) x=(ll)x*a%mo; return x; }void P(int *a, int n) { for(int i=n-1; i>=0; --i) printf("%d ", a[i]); puts(""); }void fft_init() {	G[21]=ipow(n_G, (mo-1)/(1<<21)); nG[21]=ipow(G[21], mo-2);	for(int i=20; i; --i) G[i]=(ll)G[i+1]*G[i+1]%mo, nG[i]=(ll)nG[i+1]*nG[i+1]%mo;}int getlen(int n) {	int len=1, b=-1;	for(; len
      
       >1]>>1)|((i&1)<
       
        >1, wn=G[now], w, u, v; if(f) wn=nG[now];		for(int i=0; i
        
         >1);	static int c[N], d[N];	memcpy(c, a, sizeof(int)*(n)); memcpy(d, b, sizeof(int)*((n+1)>>1));	int len=getlen(n+n-1), nlen=ipow(len, mo-2);	fft(c, len, 0); fft(d, len, 0);	for(int i=0; i
        
       
      
     

　　

多项式开根：

#include 
     
      using namespace std;typedef long long ll;const int N=(1e5+10)*4, mo=998244353;int two, G[30], nG[30], rev[N];int ipow(int a, int b) { int x=1; for(; b; b>>=1, a=(ll)a*a%mo) if(b&1) x=(ll)x*a%mo; return x; }void fft_init() {	two=ipow(2, mo-2); G[23]=ipow(3, (mo-1)/(1<<23)); nG[23]=ipow(G[23], mo-2);	for(int i=22; i; --i) G[i]=(ll)G[i+1]*G[i+1]%mo, nG[i]=(ll)nG[i+1]*nG[i+1]%mo;}int getlen(int n) {	int len=1, bl=-1;	for(; len
      
       >1]>>1)|((i&1)<
       
        >1, w=1, wn=G[now], u, v; if(f) wn=nG[now];		for(int i=0; i
        
         >1);	static int c[N], d[N];	memcpy(c, a, sizeof(int)*(n)); memcpy(d, b, sizeof(int)*((n+1)>>1));	int len=getlen(n+n-1), nlen=ipow(len, mo-2);	fft(c, len, 0); fft(d, len, 0);	for(int i=0; i
         
          >1);	static int c[N], d[N];	memcpy(c, a, sizeof(int)*(n));	getinv(b, d, n);	int len=getlen(n+n-1), nlen=ipow(len, mo-2);	fft(c, len, 0); fft(d, len, 0);	for(int i=0; i