NTT功能与实现

NTT的基础功用与拓展功能:

1.evaluate和interpolate

evaluate的本质是选择n个点(假设f(x)的度为n)，计算得到其值，因此根据定义可以直接进行代入计算。为了加快计算的过程选取$w_n$的幂次(DFT问题即离散傅里叶变换)，使用FFT算法来加快计算过程，将上述方法记作$NTT(f)$

interpolate的本质是根据n个点值计算得到对应的系数，据此可以列出方程直接求解或者利用矩阵进行求解（根据插值多项式的唯一性，解唯一）。为了加快计算的过程，当点值中的点都为$w_n$的幂次时，可以使用$FF{T}^{-1}$来进行计算，将上述方法记作$NT{T}^{-1}(f)$

注:关于$w_n$的选择
根据$w_n$的定义，要求$w_n^0$,$w_n^1$…$w_n^{n-1}$互不相同且$w_n^n=1$，当f(x)的数值需要mod N时，则需要找到$w_n^n$同余1模上N。

FFT算法实现

P3803 【多项式乘法FFT】

#include<iostream>
#include<cmath>
using namespace std;
#define NMAX 10000007
int n, m;
int rev[NMAX];
struct complex {//复数类double x, y;//x+y*i的格式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, x*b.y + y*b.x);}
};
struct complex f[NMAX], g[NMAX];//需要在复数域上进行计算
struct complex Wn(int n,int type) {//n代表的是等分的分数,type为1代表返回Wn，type为-1代表返回Wn^(-1)double Pi = acos(-1.0);return complex(cos(2 * Pi / n), type * sin(2 * Pi / n));};
void test_for_complex() {complex a = complex(1, 1);complex b = complex(2, 2);printf("%f+i*%f\n", a.x, a.y);printf("%f+i*%f\n", b.x, b.y);complex c = a + b;printf("%f+i*%f\n", c.x, c.y);c = a - b;printf("%f+i*%f\n", c.x, c.y);c = a * b;printf("%f+i*%f\n", c.x, c.y);
}
void FFT(complex *a,int deg,int deg_len,int type) {//1.进行比特反转for (int i = 0; i < deg; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (deg_len - 1));//for (int i = 0; i < deg; i++) cout << rev[i] << " ";for (int i = 0; i < deg; i++) {if(i<rev[i]) swap(a[i],a[rev[i]]);//注意这里只能交换一次}//2.进行迭代计算for (int m = 2; m <= deg; m <<= 1) {//m代表的是合并后的个数//2.1获取原根struct complex wn = Wn(m, type);for (int k = 0; k < deg; k += m) {//k代表的是待处理组(a[k...k+m-1])的第一个位置//2.2对于每一组a[k...k+m/2-1]+a[k+m/2...k+m-1]=a[k...k+m-1]complex w = complex(1, 0);for (int j = 0; j < m / 2; j++) {//k+j指向a[k...k+m/2-1]complex t = w * a[k + j + m / 2];complex u = a[k + j];a[k + j] = t + u;a[k + j + m / 2] = u - t;w = wn * w;}}}}
int main() {cin >> n >> m;for (int i = 0; i < n+1; i++) cin >> f[i].x;for (int j = 0; j < m+1; j++) cin >> g[j].x;//确定等分的分数（由于需要进行加速，所以分数应为2^n的形式）int num = 1, len = 0;while (num < (n + m+1)) {num <<=  1;len++;}FFT(f, num, len, 1);FFT(g, num, len, 1);for (int i = 0; i < num; i++) {f[i] = f[i] * g[i];}FFT(f, num,len, -1);for (int i = 0; i < n + m + 1; i++) cout << int(f[i].x/num + 0.5) << " ";
}

多项式卷积计算

#include<iostream>
#include<cmath>
#include<string>
#include<string.h>
using namespace std;
#define NMAX 102
int n, m;
int rev[NMAX];
struct complex {//复数类double x, y;//x+y*i的格式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, x*b.y + y*b.x);}
};
//struct complex f[NMAX], g[NMAX];//需要在复数域上进行计算
struct complex Wn(int n,int type) {//n代表的是等分的分数,type为1代表返回Wn，type为-1代表返回Wn^(-1)double Pi = acos(-1.0);return complex(cos(2 * Pi / n), type * sin(2 * Pi / n));};
void test_for_complex() {complex a = complex(1, 1);complex b = complex(2, 2);printf("%f+i*%f\n", a.x, a.y);printf("%f+i*%f\n", b.x, b.y);complex c = a + b;printf("%f+i*%f\n", c.x, c.y);c = a - b;printf("%f+i*%f\n", c.x, c.y);c = a * b;printf("%f+i*%f\n", c.x, c.y);
}
void FFT(complex *a,int deg,int deg_len,int type) {//1.进行比特反转for (int i = 0; i < deg; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (deg_len - 1));//for (int i = 0; i < deg; i++) cout << rev[i] << " ";for (int i = 0; i < deg; i++) {if(i<rev[i]) swap(a[i],a[rev[i]]);//注意这里只能交换一次}//2.进行迭代计算for (int m = 2; m <= deg; m <<= 1) {//m代表的是合并后的个数//2.1获取原根struct complex wn = Wn(m, type);for (int k = 0; k < deg; k += m) {//k代表的是待处理组(a[k...k+m-1])的第一个位置//2.2对于每一组a[k...k+m/2-1]+a[k+m/2...k+m-1]=a[k...k+m-1]complex w = complex(1, 0);for (int j = 0; j < m / 2; j++) {//k+j指向a[k...k+m/2-1]complex t = w * a[k + j + m / 2];complex u = a[k + j];a[k + j] = t + u;a[k + j + m / 2] = u - t;w = wn * w;}}}}void FFT_new(complex* a, int deg, int deg_len, int type) {//1.进行比特反转for (int i = 0; i < deg; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (deg_len - 1));//for (int i = 0; i < deg; i++) cout << rev[i] << " ";for (int i = 0; i < deg; i++) {if (i < rev[i]) swap(a[i], a[rev[i]]);//注意这里只能交换一次}//迭代计算for (int m = 2; m <= deg; m <<=1) {complex wn = Wn(m, type);//若为逆FTT，则为wn^(-1)for (int j = 0; j < deg; j += m) {//处理a[j...j+m-1]complex w = complex(1, 0);for (int k = 0; k < m / 2; k++) {//框定左侧为a[j...j+m/2-1]，由j+k游标指向complex t = w * a[j + k + m / 2];//旋转因子a[j + k + m / 2] = a[j + k] - t;a[j + k] = a[j + k] + t;w = wn * w;}}}//逆FTT需要乘上1/nif (type == -1) {for (int i = 0; i < deg; i++) a[i].x = int(a[i].x / deg + 0.5);}
}
int read(string input, complex * f,int start, int end) {//从string[start...end]中剥离出多项式系数int deg = 0;while(input[start] != '(') start++;//过滤掉不必要的空格使得从左括号开始double coe = 0, exp = 0;for (int i = start+1; i <= end; i++) {if (input[i] == ' ') continue;//遇到空格则直接跳过else if (input[i] == '+' || input[i] == ')') {//cout << coe << " " << exp << endl;f[int(exp)].x = coe;if (exp > deg) deg = int(exp);coe = 0, exp = 0;}else if (input[i] == 'a') {//注意可能存在系数为1的情况if (coe == 0) coe = 1;i+=2;//跳过^while (input[i] != '+' && input[i] != ')') {exp = exp * 10 + input[i++] - '0';}i--;}else coe = coe * 10 + input[i] - '0';}return deg + 1;
}
void output(complex* f,int deg) {for (int i = deg; i >= 0; i--) {if (f[i].x > 0) {if (i == 0) cout << int(f[i].x);else if (int(f[i].x) != 1)cout << int(f[i].x) << "a^" << i;else cout << "a^" << i;if (i == 0)cout << endl;else cout << "+";}}
}
int main() {string input;while (getline(cin, input)) {struct complex f[NMAX], g[NMAX];//需要在复数域上进行计算int pos =input.find('*');//根据题意，多项式的乘法仅仅只含两项int len = strlen(input.c_str());if (!(pos < len && pos >= 0)) {cout << input << endl;//不含*，则直接输出continue;}int deg_f = read(input, f,0,pos-1);int deg_g = read(input, g,pos+1,len-1);int deg = 1, deg_len = 0;while (deg < (deg_f + deg_g)) deg <<= 1, deg_len++;FFT_new(f, deg, deg_len, 1);FFT_new(g, deg, deg_len, 1);for (int i = 0; i < deg; i++) f[i] = f[i] * g[i];FFT_new(f, deg, deg_len, -1);output(f,deg);}
}

NTT算法实现

void NTT(int* a, int n, int x) {//参数设置:a代表待处理的数组，n为度,x代表的是是否是逆NTTint len = 0, cn = n;while (cn) {len++;cn >>= 1;}len--;for (RI i = 1; i < n; ++i) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));//cout <<" " << i << " "<< rev[i] << endl;}//首先进行比特反转拷贝for (RI i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);for (RI i = 1; i < n; i <<= 1) {//对于每一层RI gn = ksm(G, (mod - 1) / (i << 1)); //代表的是旋转因子for (RI j = 0; j < n; j += (i << 1)) { //以j到j+(i<<1)为一组，计算j开始的位置RI t1, t2, g = 1;for (RI k = 0; k < i; ++k, g = 1LL * g * gn % mod) {t1 = a[j + k], t2 = 1LL * g * a[j + k + i] % mod; //数组a是如何处理得到的a[j + k] = (t1 + t2) % mod, a[j + k + i] = (t1 - t2 + mod) % mod;}}}if (x == 1) return;int ny = ksm(n, mod - 2);//计算得到n^(-1)reverse(a + 1, a + n); //翻转[1...n-1]位，原因在于，求逆代入的是w^0,w^(-1),w^(-2),...w^(-n+1)// w^0,w^(n-1),w(n-2),...w^1//而此次计算代入的是w^0,w^1,w^2,...w^(n-1)，因此进行反转即可for (RI i = 0; i < n; ++i) a[i] = 1LL * a[i] * ny % mod;
}

2.计算多项式的乘法

问题概述：

计算$C(x)=A(x)\ast B(x)$

解决方法1

直接按照手算的方式，展开计算，示例代码如下所示。假设A和B的度为n，则时间复杂度为$O(n^2)$

a=[1,9]
b=[1,6]
c=[0]*(len(a)+len(b))
mod = 998244353 
for i in range(len(a)):for j in range(len(b)):c[i+j] =(c[i+j] + a[i]*b[j]) % mod
for i in range(len(c)):print(c[i])
#print(1)

解决办法2

1. 首先估算$C(x)$的度为$de{g}_c$
2. 计算得到$deg$,使得$deg=2^i$，且$deg>de{g}_c$
3. 计算向量$a=NTT(A,deg)$，向量$b=NTT(B,deg)$
4. 计算向量$c=a\ast b$
5. 向量$C=NT{T}^{-1}(c,deg)$对应了$C(x)$的各个系数

主体思想：
由于$C(x)$的度为$de{g}_c$，因此至少需要$de{g}_c$个点值来推算$C(x)$的系数，因此需要在$A(x)$和$B(x)$上至少取$de{g}_c$个点值。由于NTT要求$deg$为$2^n$，因此需要进行第1步和第2步。

#include<iostream>
using namespace std;
int read() {int q = 0; char ch = ' ';while (ch < '0' || ch>'9') ch = getchar();while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();return q;
}
#define RI register int
const int mod = 998244353, G = 3, N = 2100000;
int n;
int a[N], b[N], c[N], rev[N];
//根据小费马定理,a^(p-1) 同余 1 mod p (p为素数) a^(p-1)=a*a^(p-2)，因此a^(-1) = a^(p-2)，使用快速幂来计算a^(p-2)
int ksm(int x, int y) {//快速幂，计算x^yint re = 1;for (; y; y >>= 1, x = 1LL * x * x % mod) {if (y & 1) re = 1LL * re * x % mod;}return re;
}
void NTT(int* a, int n, int x) {//Q:为什么这里仅仅只是考虑了模式的度，而不考虑模式的具体公式//参数设置:a代表待检测的数组，n为度,x代表的是是否是逆NTTint len = 0, cn = n;while (cn) {len++;cn >>= 1;}len--;for (RI i = 1; i < n; ++i) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));//cout <<" " << i << " "<< rev[i] << endl;}//首先进行比特反转拷贝for (RI i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);for (RI i = 1; i < n; i <<= 1) {//对于每一层RI gn = ksm(G, (mod - 1) / (i << 1)); //代表的是旋转因子for (RI j = 0; j < n; j += (i << 1)) { //以j到j+(i<<1)为一组，计算j开始的位置RI t1, t2, g = 1;for (RI k = 0; k < i; ++k, g = 1LL * g * gn % mod) {t1 = a[j + k], t2 = 1LL * g * a[j + k + i] % mod; //数组a是如何处理得到的a[j + k] = (t1 + t2) % mod, a[j + k + i] = (t1 - t2 + mod) % mod;}}}if (x == 1) return;int ny = ksm(n, mod - 2);//计算得到n^(-1)reverse(a + 1, a + n); //翻转[1...n-1]位，原因在于，求逆代入的是w^0,w^(-1),w^(-2),...w^(-n+1)// w^0,w^(n-1),w(n-2),...w^1//而此次计算代入的是w^0,w^1,w^2,...w^(n-1)，因此进行反转即可for (RI i = 0; i < n; ++i) a[i] = 1LL * a[i] * ny % mod;
}void test_for_ntt() {//使用NTT计算一般的多项式乘法的注意点://1.首先需要估计结果的度，即为所有式子度之和，//2.NTT的度要求为2^n，因此需要找到最小的数，满足2^n的形式，同时需要大于估计的结果的度//3.NTT计算一般多项式乘的过程为，首先计算对于不同的函数，orz个不同的变量对应的值//然后按照计算公式计算得到对应的结果多项式在orz个不同的变量处的取值//最后逆NTT变换，得到结果多项式的系数int a[20] = { 1, 9};NTT(a, 2, 1);NTT(a, 2, -1);int b[20] = { 1, 6};NTT(b, 2, 1);NTT(b, 2, -1);int c[20];int deg = 4; //NTT中只能使用2^n来进行使用NTT(a, deg, 1);NTT(b, deg, 1);for (int i = 0; i < deg; i++) {c[i] = 1LL * a[i] * b[i] % mod;}NTT(c, deg, -1);for (int i = 0; i < deg; i++) {cout << c[i] << endl;}
}
int main()
{test_for_ntt();
}

例题

多项式乘法逆


注:公式推导过程链接

整体思路为:
为了计算mod $x^{deg}$，先计算 mod $x^{(deg+1)/2}$，然后利用公式计算mod $x^{d}eg$。具体来说，若deg为奇数，则计算$mod{x}^{(deg+1)/2}$ ,利用公式计算得到 mod $x^{deg+1}$的逆，又因为当a≡b mod $x^n$ 且n>m时，a≡b mod $x^m$，则计算结果等于模$x^{deg}$的逆；若deg为偶数，则计算mod $x^{deg/2}$，利用公式计算得到mod $x^{deg}$

#include<iostream>
using namespace std;
int read() {int q = 0; char ch = ' ';while (ch < '0' || ch>'9') ch = getchar();while (ch >= '0' && ch <= '9') q = q * 10 + ch - '0', ch = getchar();return q;
}
#define RI register int
const int mod = 998244353, G = 3, N = 2100000;
int n;
int a[N], b[N], c[N], rev[N];
//根据小费马定理,a^(p-1) 同余 1 mod p (p为素数) a^(p-1)=a*a^(p-2)，因此a^(-1) = a^(p-2)，使用快速幂来计算a^(p-2)
int ksm(int x, int y) {//快速幂，计算x^yint re = 1;for (; y; y >>= 1, x = 1LL * x * x % mod) {if (y & 1) re = 1LL * re * x % mod;}return re;
}
void NTT(int* a, int n, int x) {//Q:为什么这里仅仅只是考虑了模式的度，而不考虑模式的具体公式//参数设置:a代表待检测的数组，n为度,x代表的是是否是逆NTTint len = 0, cn = n;while (cn) {len++;cn >>= 1;}len--;for (RI i = 1; i < n; ++i) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));//cout <<" " << i << " "<< rev[i] << endl;}//首先进行比特反转拷贝for (RI i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]);for (RI i = 1; i < n; i <<= 1) {//对于每一层RI gn = ksm(G, (mod - 1) / (i << 1)); //代表的是旋转因子for (RI j = 0; j < n; j += (i << 1)) { //以j到j+(i<<1)为一组，计算j开始的位置RI t1, t2, g = 1;for (RI k = 0; k < i; ++k, g = 1LL * g * gn % mod) {t1 = a[j + k], t2 = 1LL * g * a[j + k + i] % mod; //数组a是如何处理得到的a[j + k] = (t1 + t2) % mod, a[j + k + i] = (t1 - t2 + mod) % mod;}}}if (x == 1) return;int ny = ksm(n, mod - 2);//计算得到n^(-1)reverse(a + 1, a + n); //翻转[1...n-1]位，原因在于，求逆代入的是w^0,w^(-1),w^(-2),...w^(-n+1)// w^0,w^(n-1),w(n-2),...w^1//而此次计算代入的是w^0,w^1,w^2,...w^(n-1)，因此进行反转即可for (RI i = 0; i < n; ++i) a[i] = 1LL * a[i] * ny % mod;
}
void work(int deg, int* a, int* b) {//为了计算mod x^deg，先计算 mod x^((deg+1)/2)，然后利用公式计算mod x^deg //若deg为奇数，则计算mod x^((deg+1)/2) ,利用公式计算得到 mod x^(deg+1)，又因为a==b mod x^n -> a==b mod x^m (n>m) ，则计算结果是可以适用于x^deg的//若deg为偶数，则计算mod x^(deg/2)，利用公式计算得到mod x^deg//公式的计算过程如下（整个计算过程不涉及mod x^n，而是利用NTT计算得到一般的多项式乘法）//使用NTT计算一般的多项式乘法的注意点://1.首先需要估计结果的度，即为所有式子度之和，此处的估计结果为2*deg，即deg<<1//2.NTT的度要求为2^n，因此需要找到最小的数，满足2^n的形式，同时需要大于估计的结果的度，此处为orz//3.NTT计算一般多项式乘的过程为，首先计算对于不同的函数，orz个不同的变量对应的值，即NTT(c, orz, 1), NTT(b, orz, 1);//然后按照计算公式计算得到对应的结果多项式在orz个不同的变量处的取值//最后逆NTT变换，得到结果多项式的系数，此处NTT(b, orz, -1);if (deg == 1) { b[0] = ksm(a[0], mod - 2); return; }work((deg + 1) >> 1, a, b);//这里为什么一定要加上1 a==b mod x^n -> a==b mod x^m (n>m)//处理度，取orz为大于2*deg的最小2^nRI len = 0, orz = 1;while (orz < (deg << 1)) orz <<= 1, ++len;cout << deg << " " << orz << endl;for (RI i = 1; i < orz; ++i) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));//cout <<" " << i << " "<< rev[i] << endl;}//将数组a复制到数组c，即c同于a mod x^degfor (RI i = 0; i < deg; ++i) c[i] = a[i];for (RI i = deg; i < orz; ++i) c[i] = 0;NTT(c, orz, 1), NTT(b, orz, 1);for (RI i = 0; i < orz; ++i)b[i] = 1LL * (2 - 1LL * c[i] * b[i] % mod + mod) % mod * b[i] % mod; //算数运算符% * /的优先级是一样的，从左到右计算即可NTT(b, orz, -1);//输出普通的多项式乘法for (RI i = 0; i < orz; ++i) printf("%d,", b[i]);cout << endl;//进行模x^deg处理for (RI i = deg; i < orz; ++i) b[i] = 0; //计算得到b mod x^degfor (RI i = 0; i < orz; ++i) printf("%d,", b[i]);cout << endl;
}
void test_for_ntt() {//使用NTT计算一般的多项式乘法的注意点://1.首先需要估计结果的度，即为所有式子度之和，//2.NTT的度要求为2^n，因此需要找到最小的数，满足2^n的形式，同时需要大于估计的结果的度//3.NTT计算一般多项式乘的过程为，首先计算对于不同的函数，orz个不同的变量对应的值//然后按照计算公式计算得到对应的结果多项式在orz个不同的变量处的取值//最后逆NTT变换，得到结果多项式的系数int a[20] = { 1, 9};NTT(a, 2, 1);NTT(a, 2, -1);int b[20] = { 1, 6};NTT(b, 2, 1);NTT(b, 2, -1);int c[20];int deg = 4; //NTT中只能使用2^n来进行使用NTT(a, deg, 1);NTT(b, deg, 1);for (int i = 0; i < deg; i++) {c[i] = 1LL * a[i] * b[i] % mod;}NTT(c, deg, -1);for (int i = 0; i < deg; i++) {cout << c[i] << endl;}
}
int main()
{//test_for_ntt();//cout << 3 % 5 * 2 << endl;n = read();for (RI i = 0; i < n; ++i) a[i] = read();work(n, a, b);for (RI i = 0; i < n; ++i) printf("%d ", b[i]);return 0;
}

3.循环卷积

#include<iostream>
#include<cmath>
#define NMAX 2000
using namespace std;
int rev[NMAX];int n, m;struct  complex {double x, y;//x+y*icomplex(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, x * b.y + y * b.x);}
}f[NMAX],g[NMAX];
struct complex Wn(int n,int type) {double Pi = acos(-1.0);return complex(cos(2 * Pi / n), type*sin(2 * Pi / n));
}
void FFT(struct complex* f, int deg, int deg_len,int type) {//ftt的逆直接取Wn^(-1)//首先进行比特反转for (int i = 0; i < deg; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (deg_len - 1));}for (int i = 0; i < deg; i++) {if (i < rev[i]) swap(f[i], f[rev[i]]);}//迭代进行计算for (int gap = 2; gap <= deg; gap <<= 1) {complex w = Wn(gap,type);for (int g_start = 0; g_start < deg; g_start += gap) {complex x = complex(1, 0);for (int start = g_start; start < g_start + gap / 2; start++) {complex u = f[start], v = f[start + gap / 2] * x;f[start] = u + v;f[start + gap / 2] = u - v;x = x * w;}}}if (type == -1) {for (int i = 0; i < deg; i++) {f[i].x = f[i].x/ deg;}}
}
class NTT {int a[NMAX] = { 1,9 }, b[NMAX] = { 1,6 };int rev[NMAX] = {0};int mod = 998244353;//模数int g = 3;//mod简化剩余系上的生成元int ksm(int a, int b, int mod) {int ret = 1;while (b) {if (b & 1) ret = ((long long )ret) * a % mod;a = ((long long )a) * a % mod;b >>= 1;}return ret;}void ntt(int* f, int deg, int deg_len, int type) {//首先进行比特反转for (int i = 0; i < deg; i++) {rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (deg_len - 1));}for (int i = 0; i < deg; i++) {if (i < rev[i]) swap(f[i], f[rev[i]]);}//迭代进行计算for (int gap = 2; gap <= deg; gap <<= 1) {int w = ksm(g, (mod - 1) / gap, mod);for (int g_start = 0; g_start < deg; g_start += gap) {int x = 1;for (int start = g_start; start < g_start + gap / 2; start++) {int u = f[start], v = (1LL * f[start + gap / 2] * x) % mod;f[start] = (u + v)% mod;f[start + gap / 2] = (u - v + mod) % mod;//做减法要加上mod来避免负数出现x = (1LL* x * w) % mod;}}}//求逆运算处理if (type == -1) {for (int i = 1; i < deg / 2; i++) swap(f[i], f[deg - i]);int inv_deg = ksm(deg, mod - 2, mod);for (int i = 0; i < deg; i++) f[i] = 1LL * f[i] * inv_deg % mod;}//结果输出展示for (int i = 0; i < deg; i++) cout << f[i] << " ";cout << endl;}
public:void test_for_ntt() {ntt(a, 4, 2, 1);ntt(b, 4, 2, 1);for (int i = 0; i < 4; i++) a[i] = (1LL *a[i] * b[i]) % mod;ntt(a, 4, 2, -1);for (int i = 0; i < 4; i++) cout << a[i] << " ";}
};void test_for_ftt() {//计算最高次数分别为n和m的多项式f(x)和g(x)的卷积cin >> n >> m;for (int i = 0; i < n + 1; i++) cin >> f[i].x;for (int j = 0; j < m + 1; j++) cin >> g[j].x;//确定等分的分数（由于需要进行加速，所以分数应为2^n的形式）int num = 1, len = 0;while (num < (n + m + 1)) {num <<= 1;len++;}FFT(f, num, len, 1);FFT(g, num, len, 1);for (int i = 0; i < num; i++) {//cout << f[i].x << " " << g[i].x << endl;f[i] = f[i] * g[i];}FFT(f, num, len, -1);for (int i = 0; i < n + m + 1; i++) cout << int(f[i].x + 0.5) << " ";
}
int main() {NTT t;t.test_for_ntt();
}