NTT功能与实现

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

1.evaluate和interpolate

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

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

注:关于 w n w_n wn​的选择
根据 w n w_n wn​的定义，要求 w n 0 w_n^{0} wn0​, w n 1 w_n^{1} wn1​… w n n − 1 w_n^{n-1} wnn−1​互不相同且 w n n = 1 w_n^{n}=1 wnn​=1，当f(x)的数值需要mod N时，则需要找到 w n n w_n^{n} wnn​同余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/n
	if (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代表的是是否是逆NTT
	int 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 ) ∗ B ( x ) C(x)=A(x)*B(x) C(x)=A(x)∗B(x)

解决方法1

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

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 ) C(x) C(x)的度为 d e g c deg_c degc​
  2. 计算得到 d e g deg deg,使得 d e g = 2 i deg=2^i deg=2i，且 d e g > d e g c deg>deg_c deg>degc​
  3. 计算向量 a = N T T ( A , d e g ) a=NTT(A,deg) a=NTT(A,deg)，向量 b = N T T ( B , d e g ) b=NTT(B,deg) b=NTT(B,deg)
  4. 计算向量 c = a ∗ b c=a*b c=a∗b
  5. 向量 C = N T T − 1 ( c , d e g ) C=NTT^{-1}(c,deg) C=NTT−1(c,deg)对应了 C ( x ) C(x) C(x)的各个系数

主体思想：
由于 C ( x ) C(x) C(x)的度为 d e g c deg_c degc​，因此至少需要 d e g c deg_c degc​个点值来推算 C ( x ) C(x) C(x)的系数，因此需要在 A ( x ) A(x) A(x)和 B ( x ) B(x) B(x)上至少取 d e g c deg_c degc​个点值。由于NTT要求 d e g deg deg为 2 n 2^n 2n，因此需要进行第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^y
	int 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代表的是是否是逆NTT
	int 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 d e g x^{deg} xdeg，先计算 mod x ( d e g + 1 ) / 2 x^{(deg+1)/2} x(deg+1)/2，然后利用公式计算mod x d e g x^deg xdeg。具体来说，若deg为奇数，则计算 m o d x ( d e g + 1 ) / 2 mod x^{(deg+1)/2} modx(deg+1)/2 ,利用公式计算得到 mod x d e g + 1 x^{deg+1} xdeg+1的逆，又因为当a≡b mod x n x^n xn 且n>m时，a≡b mod x m x^m xm，则计算结果等于模 x d e g x^{deg} xdeg的逆；若deg为偶数，则计算mod x d e g / 2 x^{deg/2} xdeg/2，利用公式计算得到mod x d e g x^{deg} xdeg

#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^y
	int 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代表的是是否是逆NTT
	int 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^n
	RI 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^deg
	for (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^deg
	for (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*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);
	}
}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();
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/101788.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

OpenGL-入门-BMP像素图glReadPixels（1）实现读取屏幕中间的颜色和获取屏幕上鼠标点击位置的颜色

OpenGL-入门-BMP像素图glReadPixels（1）实现读取屏幕中间的颜色和获取屏幕上鼠标点击位置的颜色

glReadPixels函数用于从帧缓冲区中读取像素数据。它可以用来获取屏幕上特定位置的像素颜色值或者获取一块区域内的像素数据。下面是该函数的基本语法&#xff1a; void glReadPixels(GLint x, GLint y, GLsizei width, GLsizei height, GLenum format, GLenum type, GLvoid *da…
阅读更多...
JVM内存模型

JVM内存模型

文章目录 一、前言二、JVM内存模型1、Java堆2、方法区3、Java栈3.1、局部变量表3.2、操作数栈3.3、动态链接3.4、返回地址 4、本地方法栈5、程序计数器 一、前言 本文将详细介绍JVM内存模型&#xff0c;JVM定义了若干个程序执行期间使用的数据区域。这个区域里的一些数据在JVM…
阅读更多...
手撕二叉平衡树

手撕二叉平衡树

今天给大家带来的是平衡树的代码实现&#xff0c;如下&#xff1a; #pragma once #include <iostream> #include <map> #include <set> #include <assert.h> #include <math.h> using namespace std; namespace cc {template<class K, clas…
阅读更多...
TypeScript学习 + 贪吃蛇项目

TypeScript学习 + 贪吃蛇项目

TypeSCript简介 TypeScript是JavaScript的超集。它对JS进行了扩展&#xff0c;向JS中引入了类型的概念&#xff0c;并添加了许多新的特性。TS代码需要通过编译器编译为JS&#xff0c;然后再交由JS解析器执行。TS完全兼容JS&#xff0c;换言之&#xff0c;任何的JS代码都可以直…
阅读更多...
IP地址、网关、网络/主机号、子网掩码关系

IP地址、网关、网络/主机号、子网掩码关系

一、IP地址 IP地址组成 IP地址分为两个部分&#xff1a;网络号和主机号 &#xff08;1&#xff09;网络号:标识网段&#xff0c;保证相互连接的两个网段具有不同的标识。 &#xff08;2&#xff09;主机号:标识主机&#xff0c;同一网段内&#xff0c;主机之间具有相同的网…
阅读更多...
构建稳定的爬虫系统：如何选择合适的HTTP代理服务商

构建稳定的爬虫系统：如何选择合适的HTTP代理服务商

在构建一个稳定、高效的爬虫系统中&#xff0c;选择合适的HTTP代理服务商是至关重要的一步。本文将介绍如何选取可靠且性能优秀的HTTP代理服务供应商&#xff0c;来完成搭建一个强大而稳定的爬虫系统。 1.了解不同类型和特点 -免费公开代理服务器:提供免费但可能存在限制或不…
阅读更多...
opencv鼠标事件函数setMouseCallback()详解

opencv鼠标事件函数setMouseCallback()详解

文章目录 opencv鼠标事件函数setMouseCallback()详解1、鼠标事件函数&#xff1a;&#xff08;1&#xff09;鼠标事件函数原型&#xff1a;setMouseCallback()&#xff0c;此函数会在调用之后不断查询回调函数onMouse()&#xff0c;直到窗口销毁&#xff08;2&#xff09;回调函…
阅读更多...
优秀的ui设计作品（合集）

优秀的ui设计作品（合集）

UI设计师需要了解的九个Tips 1.图片类APP排版突破 规则是死的&#xff0c;人是活的。很多时候&#xff0c;如果需求是比较宽要尝试突破原则&#xff0c;用一些另类的排版方式&#xff0c;其实也是做好设计的本质。在图片类app中&#xff0c;错落一些的排版会使你的作品更有魅力…
阅读更多...
怎么将pdf合并成一个？将pdf合并成一个的方法

怎么将pdf合并成一个？将pdf合并成一个的方法

在日常工作和学习中&#xff0c;我们经常会遇到需要将多个PDF文件合并成一个的情况。这不仅能够提高文件管理的便捷性&#xff0c;还能节省存储空间并使阅读更加流畅。那么&#xff0c;怎么将pdf合并成一个呢&#xff1f;在本文中&#xff0c;我将为您介绍几种简单实用的方法&a…
阅读更多...
xml

xml

1.xml 1.1概述【理解】 万维网联盟(W3C) 万维网联盟(W3C)创建于1994年&#xff0c;又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。 建立者&#xff1a; Tim Berners-Lee (蒂姆伯纳斯李)。 是Web技术领域最具权威和影响力的国际中立性技术标准机构。 到目前为…
阅读更多...
C++/C：pass-by-value(值传递)与pass-by-reference（引用传递）

C++/C：pass-by-value(值传递)与pass-by-reference（引用传递）

一、C的引用&#xff08;reference&#xff09; 1.1、引用的概念 c中新增了引用&#xff08;reference&#xff09;的概念&#xff0c;引用可以作为一个已定义变量的别名。 Declares a named variable as a reference, that is, an alias to an already-existing object or f…
阅读更多...
docker 笔记1

docker 笔记1

目录 1.为什么有docker ? 2.Docker 的核心概念 3.容器与虚拟机比较 3.1传统的虚拟化技术 3.2容器技术 3.3Docker容器的有什么作用&#xff1f; 3.4应用案例 4. docker 安装下载 4.1CentOS Docker 安装 4.2 Docker的基本组成 &#xff1f;&#xff08;面试&#xff09…
阅读更多...
2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书海口经济学院图书馆

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书海口经济学院图书馆

2023开学礼《乡村振兴战略下传统村落文化旅游设计》许少辉八一新书海口经济学院图书馆
阅读更多...
基于 Debian 12 的 Devuan GNU+Linux 5 为软件自由爱好者而生

基于 Debian 12 的 Devuan GNU+Linux 5 为软件自由爱好者而生

导读Devuan 开发人员宣布发布 Devuan GNULinux 5.0 “代达罗斯 “发行版&#xff0c;它是 Debian GNU/Linux 操作系统的 100% 衍生版本&#xff0c;不包含 systemd 和相关组件。 Devuan GNULinux 5 基于最新的 Debian GNU/Linux 12 “书虫 “操作系统系列&#xff0c;采用长期支…
阅读更多...
路由器的简单概述(详细理解+实例精讲)

路由器的简单概述(详细理解+实例精讲)

系列文章目录 华为数通学习&#xff08;4&#xff09; 目录 系列文章目录 华为数通学习&#xff08;4&#xff09; 前言 一&#xff0c;网段间通信 二&#xff0c;路由器的基本特点 三&#xff0c;路由信息介绍 四&#xff0c;路由表 五&#xff0c;路由表的来源有哪些…
阅读更多...
【笔记】常用 js 函数

【笔记】常用 js 函数

数组去重 Array.from(new Set()) 对象合并 Object.assign . 这里有个细节&#xff1a;当两个对象中含有key相同value不同时&#xff0c;会以 后面对象的key&#xff1a;value为准 保留小数点后几位 toFixed 注意&#xff1a; Number型&#xff0c;用该方法处理完&#xff0c;会…
阅读更多...
前端开发之Element Plus的分页组件el-pagination显示英文转变为中文

前端开发之Element Plus的分页组件el-pagination显示英文转变为中文

前言 在使用element的时候分页提示语句是中文的到了element-plus中式英文的&#xff0c;本文讲解的就是怎样将英文转变为中文 效果图 解决方案 如果你的element-plus版本为2.2.29以下的 import { createApp } from vue import App from ./App.vue import ElementPlus from …
阅读更多...
react css 污染解决方法

react css 污染解决方法

上代码 .m-nav-bar {background: #171a21;.content {height: 104px;margin: 0px auto;} }import React from "react"; import styles from ./css.module.scssexport default class NavBar extends React.Component<any, any> {constructor (props: any) {supe…
阅读更多...
详解 SpringMVC 中获取请求参数

详解 SpringMVC 中获取请求参数

文章目录 1、通过ServletAPI获取2、通过控制器方法的形参获取请求参数3、[RequestParam ](/RequestParam )4、[RequestHeader ](/RequestHeader )5、[CookieValue ](/CookieValue )6、通过POJO获取请求参数7、解决获取请求参数的乱码问题总结 在Spring MVC中&#xff0c;获取请…
阅读更多...
gnuradio-hackrf_info.exe -FM频率使用

gnuradio-hackrf_info.exe -FM频率使用

97910000
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站