• 欢迎光临~

# 多项式基本操作

FFT：在(O(nlogn))的时间内实现多项式的系数表示形式与点值表示形式的转换，作用域：实数

NTT：在(O(nlogn))的时间内实现多项式的系数表示形式与点值表示形式的转换，作用域：有原根的模

MTT:

[考虑一个n次多项式F(x) = sum_{i = 1}^nx^ia_i\ 考虑怎么快速求出其n个不重合的点的点值\ ]

[不妨考虑n为二次整数次幂\ F(x) = sum_{i = 0}^{n - 1} x^ia_i = (x^0a_0 + ...+x^{n - 1}a_{n - 1})\ = x^0a_0 + x^2_2 + ...+x^{n - 2}a_{n - 2} + x (x^0a_1 + x^2a_3+...+x^{n - 1}a_{n - 1})\ F_1(x) = a_0 + a_2x^1 + ... +a_{n - 2}x^{frac{n}{2} - 1}\ F_2(x) = a_1 + a_3x^1 + ... +a_{n - 1}x^{frac{n}{2} - 1}\ F(x) = F_1(x^2) + xF_2(x^2)\ 将一个单位根w_n^k带进去\ F(w_n^k) = F_1(w_n^{2k}) + w_n^kF_2(w^{2k}_n)\ 又因为单位根有一个性质:w_{2n}^{2k} = w^k_n\ k < frac{n}{2}\ 有F(w_n^k) = F_1(w_{frac{n}{2}}^{k}) + w_n^kF_2(w^{k}_{frac{n}{2}})\ F(w_n^{k + frac{n}{2}}) = F_1(w_{frac{n}{2}}^{k}) - w_n^kF_2(w^{k}_{frac{n}{2}})\ 发现每一次把问题分成了一半，统计是O(n)的\ 故总的复杂度为O(nlogn)\ ]

[w_n^{k + frac{n}{2}} = -w_n^k ]

[F(w_n^{0}) , F(w_n^{-1}),F(w_n^{-2})...,F(w_n^{-{n - 1}})\ G(w_n^{-k}) = sum_{i = 0}^{n - 1}F(w_n^i)w_n^{-ik}\ =sum_{i = 0}^{n - 1} (sum_{j = 0}^{n - 1}a_jw_n^{ij}) w_n^{-ik}\ = sum_{j = 0}^{n - 1}a_jsum_{i = 0}^{n - 1}w_n^iw_n^{(j - k)}\ 发现后面这个式子实际上是一个等比数列求和\ 于是可以推导得 后面这个式子只有\ j = k : n\ j != k : 0\ 有sum_{j = 0}^{n - 1}a_jsum_{i = 0}^{n - 1}w_n^iw_n^{(j - k)}\ =n*a_k\ 故a_k = frac{G(w_n^k)}{n} ]

[000,001,010,011,100,101,110,111\ ->\ 000,100,010,110,001,101,011,111\ ]

[f[i] = f[i >> 1] + (i & 1) << (log_2n - 1) ]

``````#include<bits/stdc++.h>
#define MAXN 2000005
typedef double ll;
const ll PI = acos(-1.0);
using namespace std;

int n,m;
int lim,len;
int res[MAXN];

struct node{ll dx,dy;}a[MAXN],b[MAXN],c[MAXN];
node operator + (node A , node B){return (node){A.dx + B.dx , A.dy + B.dy};}
node operator - (node A , node B){return (node){A.dx - B.dx , A.dy - B.dy};}
node operator * (node A , node B){return (node){A.dx * B.dx - A.dy * B.dy , A.dx * B.dy + A.dy * B.dx};}

node wn(double sz , int tp){
ll zz = 2.0 * PI / sz;
if(tp == (-1))return (node){cos(zz) , -sin(zz)};
return (node){cos(zz) , sin(zz)};
}

void fft(node f[] , int tp){
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
node w1 = wn(k << 1 , tp) , w , A , B;
for(int i = 0 ; i < len ; i = i + k + k){
w = (node){1 , 0};
for(int j = 0 ; j < k ; j++ , w = w * w1){
A = f[i + j] , B = f[i + j + k] * w;
f[i + j] = A + B;
f[i + j + k] = A - B;
}
}
}
if(tp == (-1))for(int i = 0 ; i < len ; i++)f[i].dx /= (len * 1.0);

}

int main(){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i <= n ; i++)scanf("%lf" , &a[i].dx);
for(int i = 0 ; i <= m ; i++)scanf("%lf" , &b[i].dx);
len = 1 , lim = 0;
while(len <= (n + m + 2))len = len + len , lim++;
for(int i = 1 ; i < len ; i++){
res[i] = (res[i >> 1] >> 1) | ((i & 1) << (lim - 1));
}
fft(a , 1);
fft(b , 1);
for(int i = 0 ; i < len ; i++)c[i] = a[i] * b[i];
fft(c , -1);
for(int i = 0 ; i < n + m + 1 ; i++)printf("%d " , (int)(c[i].dx + 0.5));

}
``````

(w_n = g^{frac{p - 1}{n}} mod p)

``````#include<bits/stdc++.h>
#define MAXN 5000005
typedef long long ll;
const ll mod = 998244353;
const ll g = 3;
using namespace std;

int n,m,limit,len;
ll a[MAXN],b[MAXN],c[MAXN];
int res[MAXN];

int poww(ll x , int y){
ll zz = 1;
while(y){
if(y & 1)zz = 1ll * x * zz % mod;
x = (1ll * x * x) % mod;
y = y >> 1;
}
return zz;
}

//wn =

void NTT(ll f[] , int tp){
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
if(tp == (-1))w1 = poww(w1 , mod - 2);
for(int i = 0 ; i < len ; i = i + k + k){
w = 1;
for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
A = f[i + j] , B = f[i + j + k] * w % mod;
f[i + j] = ((A + B) % mod + mod) % mod;
f[i + j + k] = ((A - B) % mod + mod) % mod;
}
}
}
if(tp == 1)return;
ll zz = poww(len , mod - 2);
for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;

}

int main(){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i <= n ; i++)scanf("%lld" , &a[i]);
for(int i = 0 ; i <= m ; i++)scanf("%lld" , &b[i]);
len = 1 , limit = 0;
while(len <= (n + m + 1))len = len + len , limit++;
for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
NTT(a , 1);
NTT(b , 1);
for(int i = 0 ; i < len ; i++)c[i] = 1ll * a[i] * b[i] % mod;
NTT(c , -1);
for(int i = 0 ; i < n + m + 1 ; i++)printf("%lld " , c[i]);

}
``````

#### P1919 【模板】A*B Problem 升级版（FFT 快速傅里叶变换）

``````#include<bits/stdc++.h>
#define MAXN 5000005
typedef long long ll;
const ll mod = 998244353;
const ll g = 3;
using namespace std;

int n,m,limit,len,res[MAXN];
ll a[MAXN],b[MAXN],c[MAXN];
int sz;
char s[MAXN];

ll poww(ll x , int y){
ll zz = 1;
while(y){
if(y & 1)zz = zz * x % mod;
x = x * x % mod;
y = y >> 1;
}
return zz;
}

void NTT(ll f[] , int tp){
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
if(tp == (-1))w1 = poww(w1 , mod - 2);
for(int i = 0 ; i < len ; i = i + k + k){
w = 1;
for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
A = f[i + j] , B = f[i + j + k] * w % mod;
f[i + j] = ((A + B) % mod + mod) % mod;
f[i + j + k] = ((A - B) % mod + mod) % mod;
}
}
}
if(tp == 1)return;
ll zz = poww(len , mod - 2);
for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

int main(){
scanf("%s" , s) , sz = strlen(s) , n = sz - 1;
for(int i = 0 ; i <= n ; i++)a[i] = s[n - i] - '0';
scanf("%s" , s) , sz = strlen(s) , m = sz - 1;
for(int i = 0 ; i <= m ; i++)b[i] = s[m - i] - '0';

len = 1 , limit = 0;
while(len <= (n + m + 4)){
len = len + len , limit++;
}
for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));

NTT(a , 1);
NTT(b , 1);
for(int i = 0 ; i < len ; i++)c[i] = (a[i] * b[i] % mod + mod) % mod;
NTT(c , -1);

for(int i = 0 ; i < n + m + 1 ; i++){
c[i + 1] = c[i + 1] + c[i] / 10 , c[i] %= 10;
}
int len = n + m + 1;
while(c[len] >= 10)c[len + 1] = c[len + 1] + c[len] / 10 , c[len] %= 10 , len++;
while(c[len] == 0)len--;
for(int i = len ; i >= 0 ; i--)cout<<c[i];

}
``````

[给定序列g_{1...n - 1},求序列f_{0...n - 1}\ f_i = sum_{j = 1}^if_{i - j}g_j , f_0 = 1\ 对于模数998244353取模 ]

[f_i += sum_{j = l}^{mid}f_j * g_{i - j} ]

``````#include<bits/stdc++.h>
#define MAXN 500005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n;
ll g[MAXN],ans[MAXN];
ll poww(ll x , int y){
ll zz = 1;
while(y){
if(y & 1)zz = zz * x % mod;
x = x * x % mod;
y = y >> 1;
}
return zz;
}

int limit,len;
ll a[MAXN],b[MAXN],res[MAXN];

void NTT(ll f[] , int tp){
for(int i = 1 ; i < len ; i++)res[i] = ((res[i >> 1] >> 1) | ((i & 1) << (limit - 1)));
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
if(tp == (-1))w1 = poww(w1 , mod - 2);
for(int i = 0 ; i < len ; i = i + k + k){
w = 1;
for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
A = f[i + j] , B = f[i + j + k] * w % mod;
f[i + j] = ((A + B) % mod + mod) % mod;
f[i + j + k] = ((A - B) % mod + mod) % mod;
}
}
}
if(tp == 1)return;
ll zz = poww(len , mod - 2);
for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void cdq(int l , int r){
if(l == r)return;
int mid = (l + r) >> 1;
cdq(l , mid);
for(int i = l ; i <= mid ; i++)a[i - l] = ans[i] , b[i - l] = g[i - l];
for(int i = mid + 1 ; i <= r ; i++)a[i - l] = 0 , b[i - l] = g[i - l];
len = 1 , limit = 0;
while(len <= (r - l + 1))len = len + len , limit++;
for(int i = r - l + 1 ; i <= len ; i++)a[i] = b[i] = 0;
NTT(a , 1) , NTT(b , 1);
for(int i = 0 ; i < len ; i++)a[i] = (a[i] * b[i] % mod + mod) % mod;
NTT(a , -1);
for(int i = mid + 1 ; i <= r ; i++)ans[i] = (ans[i] + a[i - l]) % mod;
cdq(mid + 1 , r);

}

int main(){
scanf("%d" , &n) , ans[0] = 1;
for(int i = 1 ; i < n ; i++)scanf("%d" , &g[i]);
len = 1;while(len < n)len = len + len;
cdq(0 , len - 1);
for(int i = 0 ; i < n ; i++)cout<<ans[i]<<" ";
}
``````

#### 任意模数多项式乘法(MTT)

1.把答案在三个有原根的模数下求出来，然后对于每一个答案都做一次CRT，9次

2.分解每一个数成(sqrt{mod} * p + q = a_i)的形式 , 然后做多项式乘法暴力乘

3.MTT（论文里面的玩意）

``````#include<bits/stdc++.h>
#define MAXN 400005
typedef long double ll;
typedef long long LL;
const ll PI = acos(-1.0);
using namespace std;

int n,m,limit,len;
int res[MAXN];
LL ans[MAXN],part = 32768,p;
struct node{ll dx,dy;}a1[MAXN],b1[MAXN],a2[MAXN],b2[MAXN],X[MAXN];

node operator + (node A , node B){return (node){A.dx + B.dx , A.dy + B.dy};}
node operator - (node A , node B){return (node){A.dx - B.dx , A.dy - B.dy};}
node operator * (node A , node B){return (node){A.dx * B.dx - A.dy * B.dy , A.dx * B.dy + A.dy * B.dx};}

node wn(ll sz , int tp){
ll zz = 2.0 * PI / sz;
if(tp == (-1))return (node){cos(zz) , -sin(zz)};
return (node){cos(zz) , sin(zz)};
}

void fft(node f[] , int tp){
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
node w1 = wn(k << 1 , tp) , w , A , B;
for(int i = 0 ; i < len ; i = i + k + k){
w = (node){1 , 0};
for(int j = 0 ; j < k ; j++ , w = w * w1){
A = f[i + j] , B = f[i + j + k] * w;
f[i + j] = A + B;
f[i + j + k] = A - B;
}
}
}
}

void solve(node A[] , node B[] , LL res){
for(int i = 0 ; i < len ; i++)X[i].dx = X[i].dy = 0;
for(int i = 0 ; i < len ; i++)X[i] = A[i] * B[i];
fft(X , -1);
for(int i=0;i<=n+m;++i)(ans[i]+=(LL)(X[i].dx/len+0.5)%p*res%p)%=p;
}

void MTT(node f1[] , node f2[] , node g1[] , node g2[]){
fft(f1 , 1) , fft(f2 , 1) , fft(g1 , 1) , fft(g2 , 1);
solve(f1 , g1 , part * part);
solve(f1 , g2 , part);
solve(f2 , g1 , part);
solve(f2 , g2 , 1);
for(int i = 0 ; i <= n + m ; i++){
cout<<(ans[i] % p + p) % p<<" ";
}
}

int main(){
scanf("%d%d%lld" , &n , &m , &p);LL zz;
for(int i = 0 ; i <= n ; i++){
scanf("%lld" , &zz);
a1[i].dx = zz / part;
a2[i].dx = zz % part;
}
for(int i = 0 ; i <= m ; i++){
scanf("%lld" , &zz);
b1[i].dx = zz / part;
b2[i].dx = zz % part;
}
len = 1 , limit = 0;
while(len <= (n + m + 2))len = len + len , limit++;
for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
MTT(a1 , a2 , b1 , b2);

}
``````

#### 多项式乘法逆

[F(x)H(x) = 1 (mod x^{frac{n}{2}})\ F(x)H(x) = 1 (mod x^{frac{n}{2}})\ 有F(x)G(x) = 1 (mod x^{frac{n}{2}})\ 有F(x)(G(x) - H(x)) = 0 (mod x^{frac{n}{2}})\ 平方有G^2(x) + H^2(x) = 2H(x)G(x) (mod x^n)\ 两边再同时乘上F(x)\ G(x) = 2H(x) - H^2(x)F(x) (mod x^n)\ ]

``````#include<bits/stdc++.h>
#define MAXN 400005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n,len,limit,res[MAXN];
ll a[MAXN],c[MAXN];
ll H[MAXN],G[MAXN];

ll poww(ll x , int y){
ll zz = 1;
while(y){
if(y & 1)zz = zz * x % mod;
x = x * x % mod;
y = y >> 1;
}
return zz;
}

void NTT(ll f[] , int tp){
for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
if(tp == (-1))w1 = poww(w1 , mod - 2);
for(int i = 0 ; i < len ; i = i + k + k){
w = 1;
for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
A = f[i + j] , B = f[i + j + k] * w % mod;
f[i + j] = ((A + B) % mod + mod) % mod;
f[i + j + k] = ((A - B) % mod + mod) % mod;
}
}
}
if(tp == 1)return;
ll zz = poww(len , mod - 2);
for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void solve(int LEN , int L){
if(LEN == 1)return (void)(G[0] = poww(a[0] , mod - 2));
solve((LEN + 1) >> 1 , L - 1);
swap(H , G);
len = 1 , limit = 0;
while(len < (LEN << 1))len = len << 1 , limit++;
for(int i = 0 ; i < LEN ; i++)G[i] = c[i] = 0;
for(int i = 0 ; i < LEN ; i++)c[i] = a[i];
for(int i = LEN ; i < len ; i++)c[i] = 0;
NTT(c , 1) , NTT(H , 1);
for(int i = 0 ; i < len ; i++)G[i] = ((H[i] * ((2ll - H[i] * c[i]) % mod + mod) % mod) % mod + mod) % mod;
NTT(G , -1);
for(int i = LEN ; i < len ; i++)G[i] = 0;
}

int main(){
scanf("%d" , &n);for(int i = 0 ; i < n ; i++)scanf("%lld" , &a[i]);
solve(n , limit);
for(int i = 0 ; i < n ; i++)cout<<G[i]<<" ";
}

``````

#### 多项式ln

[G(x) = ln(A(x))\ G'(x) = frac{A'(x)}{A(X)}\ G(x) = int G'(x) = int frac{A'(x)}{A(X)}\ 直接对右边这个玩意多项式求逆+求导+积分一下就好了 ]

``````#include<bits/stdc++.h>
#define MAXN 400005
typedef long long ll;
const ll mod = 998244353;
using namespace std;

int n,m,len,limit,res[MAXN];
ll a[MAXN],c[MAXN];
ll H[MAXN],G[MAXN];

ll poww(ll x , int y){
ll zz = 1;
while(y){
if(y & 1)zz = zz * x % mod;
x = x * x % mod;
y = y >> 1;
}
return zz;
}

void NTT(ll f[] , int tp){
for(int i = 1 ; i < len ; i++)res[i] = (res[i >> 1] >> 1) | ((i & 1) << (limit - 1));
for(int i = 0 ; i < len ; i++)if(i < res[i])swap(f[i] , f[res[i]]);
for(int k = 1 ; k < len ; k = k + k){
ll w1 = poww(3 , (mod - 1) / (k << 1)) , w , A , B;
if(tp == (-1))w1 = poww(w1 , mod - 2);
for(int i = 0 ; i < len ; i = i + k + k){
w = 1;
for(int j = 0 ; j < k ; j++ , w = w * w1 % mod){
A = f[i + j] , B = f[i + j + k] * w % mod;
f[i + j] = ((A + B) % mod + mod) % mod;
f[i + j + k] = ((A - B) % mod + mod) % mod;
}
}
}
if(tp == 1)return;
ll zz = poww(len , mod - 2);
for(int i = 0 ; i < len ; i++)f[i] = (1ll * f[i] * zz) % mod;
}

void solve(int LEN){
if(LEN == 1)return (void)(G[0] = poww(a[0] , mod - 2));
solve((LEN + 1) >> 1);
swap(H , G);
len = 1 , limit = 0;
while(len < (LEN << 1))len = len << 1 , limit++;
for(int i = 0 ; i < LEN ; i++)G[i] = c[i] = 0;
for(int i = 0 ; i < LEN ; i++)c[i] = a[i];
for(int i = LEN ; i < len ; i++)c[i] = 0;
NTT(c , 1) , NTT(H , 1);
for(int i = 0 ; i < len ; i++)G[i] = ((H[i] * ((2ll - H[i] * c[i]) % mod + mod) % mod) % mod + mod) % mod;
NTT(G , -1);
for(int i = LEN ; i < len ; i++)G[i] = 0;
}

int main(){
scanf("%d" , &n) , m = n - 1;for(int i = 0 ; i < n ; i++)scanf("%lld" , &a[i]);
solve(n);memset(H , 0 , sizeof(H));
for(int i = 1 ; i < n ; i++)H[i - 1] = ((a[i] * (1ll * i)) % mod + mod) % mod;
len = 1 , limit = 0;
while(len <= (n + m + 1))len = len + len , limit++;
NTT(H , 1) , NTT(G , 1);
for(int i = 0 ; i < len ; i++)H[i] = (H[i] * G[i] % mod + mod) % mod;
NTT(H , -1);memset(G , 0 , sizeof(G));
for(int i = 0 ; i < len ; i++){
G[i + 1] = (H[i] * poww(i + 1 , mod - 2) % mod + mod) % mod;
}
for(int i = 0 ; i < n ; i++)cout<<G[i]<<" ";

}
``````

#### 实数域上的牛顿迭代

[求函数F(x)的零点\ 先大致故一下零点在哪里\ 在零点附近取一个点(x_0 , F(x_0))\ 在该点做一条切线与x轴相切 k = F'(x_0)\ 交点为x_1\ 即y - F(x_0) = F'(x_0)(x - x_0)\ frac{0 - F(x_0)}{F'(x_0)} + x_0 = x_1 ]

#### 函数域上的牛顿迭代，虽然上下两个部分关系并不大，但思想是类似的

[给定一个F(x),让你求一个多项式f .st F(f) = 0\ 考虑倍增构造\ F(f) = 0 (mod x^n) , f_0 = f (mod x^n)\ 考虑F(f)在f = f_0除的泰勒展开\ F(f) = sum_{k = 0}frac{F^{k}(f - f_0)^k}{k!}\ k >= 2时，(f - f_0) ^ k = 0 (mod x^{2*n})显然\ 则有 F(f) = 0 = F(f_0) + F'(f_0)(f - f_0) (mod x^{2n})\ 则f = f_0 - frac{F(f_0)}{F'(f_0)} (mod x^{2n})\ 如此下去就可以得到f ]

### 注意，这里的f虽然是函数，但我们把它当成常数来处理

#### 多项式exp

[B(x) = e^{A(x)}\ 两边取对数 ln(B(x)) = A(x) \ ln(B(x)) - A(x) = 0\ 构造函数F(f) = ln(f) - A(x) \ 采用牛顿迭代得到这个f就好了\ 即f = (1 + A(x) - ln(f_0))*f_0 ]

#### 多项式开方

[B(x) = sqrt{A(x)}\ B^2(x) = A(x)\ B^2(x) - A(x) = 0\ 构造函数F(f) = f^2 - A(x) = 0\ 即f = frac{f_0^2 + A(f_0)}{2f_0} 直接套用牛顿迭代就好了 ]

#### 下降幂多项式乘法

[A(x) = sum_{i = 0}a_ix^{underline{i}}这个个下降幂多项式的例子 ]