多项式

这里是一些模板然而并不会写教程

蝴蝶操作

1
2
3
4
5
6
7
8
9
int r[maxn], l, lim;
inline void init(int len, int type = 1) {
if (type) {
lim = 1, l = 0;
while (lim <= len) lim <<= 1, l++;
} else
lim = 1 << len, l = len;
rep(i, 0, lim - 1) r[i] = ((r[i >> 1] >> 1) | ((i & 1) << (l - 1)));
}

$FFT$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const double Pi=acos(-1.0);
struct complex
{
double x,y;
complex (double xx=0,double yy=0){x=xx,y=yy;}
complex operator + (const complex &B)
{return complex(x+B.x,y+B.y);}
complex operator - (const complex &B)
{return complex(x-B.x,y-B.y);}
complex operator * (const complex &B)
{return complex(x*B.x-y*B.y,B.x*y+x*B.y);}
}a[maxn],b[maxn];
int n,m,r[maxn],l,lim;
void FFT(complex *A,int type)
{
rep(i,0,lim-1)
if (i<r[i]) swap(A[i],A[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
complex Wn(cos(Pi/mid),type*sin(Pi/mid));
for(int R=mid<<1,j=0;j<lim;j+=R){
complex w(1,0);
for(int k=0;k<mid;k++,w=w*Wn){
complex x=A[j+k],y=w*A[j+mid+k];
A[j+k]=x+y;
A[j+mid+k]=x-y;
}
}
}
}

$NTT$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
inline int qpow(int x,int k)
{
int ans=1;
for(;k;x=1ll*x*x%mod,k>>=1) if (k&1) ans=1ll*ans*x%mod;
return ans;
}
inline int Mod(int x){return x<0?x+mod:(x>=mod?x-mod:x);}
int lim,r[100005],l;
void NTT(int *a,int type)
{
rep(i,0,lim-1) if (i<r[i]) swap(a[i],a[r[i]]);
for(int mid=1;mid<lim;mid<<=1){
int Wn=qpow(g,(mod-1)/(mid<<1));
if (type==-1) Wn=qpow(Wn,mod-2);
for(int R=mid<<1,j=0;j<lim;j+=R){
for(int k=0,w=1;k<mid;k++,w=1ll*w*Wn%mod){
int x=a[j+k],y=1ll*w*a[j+k+mid]%mod;
a[j+k]=Mod(x+y);
a[j+k+mid]=Mod(x-y);
}
}
}
if (type==-1){
int x=qpow(lim,mod-2);
rep(i,0,lim-1) a[i]=1ll*a[i]*x%mod;
}
}

分治NTT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void mul(int *a,int *b)
{
NTT(a,1),NTT(b,1);
rep(i,0,lim-1) a[i]=1ll*a[i]*b[i]%mod;
NTT(a,-1);
}
inline void init(int n)
{
lim=1,l=0;
while(lim<=n)lim=lim<<1,++l;
rep(i,0,lim-1) r[i]=((r[i>>1]>>1)|((i&1)<<(l-1))),A[i]=B[i]=0;
}
void cdqNTT(int l,int r)
{
if (l==r) return ;
int mid=(l+r)>>1;
cdqNTT(l,mid);
init(r-l+1);
rep(i,l,mid) A[i-l]=a[i];
rep(i,0,r-l) B[i]=b[i];
mul(A,B);
rep(i,mid+1,r) a[i]-=A[i-l],a[i]=a[i]<0?a[i]+mod:a[i];
cdqNTT(mid+1,r);
}

多项式求逆

$$
n==1:
\
f(x) \equiv c (mod\ x)\ \ \ \ \ \ c为常数
\
f^{-1} \equiv c^{-1} (mod\ x)
\
n>1:
\
f(x)g(x) \equiv 1 (mod\ x^n)
\

f(x)g’(x) \equiv 1 (mod\ x^{\lceil\frac{n}{2}\rceil})
\
f(x)g(x) \equiv 1 (mod\ x^{\lceil\frac{n}{2}\rceil})
\
以上两式相减
\
g(x)-g’(x) \equiv 0 (mod\ x^{\lceil\frac{n}{2}\rceil})
\
两边平方
\
g^2(x)-2g’(x)g(x)+g’^2(x)\equiv 0(mod\ x^n)
\
同乘f(x)
\
g(x)\equiv 2g’(x)-f(x)g’^2(x)(mod x^n)
\
时间复杂度:
T(n)=T(\frac{n}{2})+O(n log n)=O(n log n)
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(int n)
{
if (n==1){
G[0]=qpow(F[0],mod-2);
return ;
}
solve((n+1)>>1);
init(n*2);
rep(i,0,n-1) A[i]=F[i];
rep(i,n,lim-1) A[i]=0;
NTT(A,1),NTT(G,1);
rep(i,0,lim-1)
G[i]=1ll*Mod(2-1ll*A[i]*G[i]%mod)*G[i]%mod;
NTT(G,-1);
rep(i,n,lim-1) G[i]=0;
}

$MTT$

此坑待填

avatar
contest0110

  1. 1. 蝴蝶操作
  2. 2. $FFT$
  3. 3. $NTT$
  4. 4. 分治NTT
  5. 5. 多项式求逆
  6. 6. $MTT$