MnZn 求助 NTT 板子
查看原帖
MnZn 求助 NTT 板子
232838
huangkx楼主2022/9/5 09:39

RT,样例输出全是 00,求大佬帮忙调一下,应该码风还可以看。

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int G = 3;
const int MAXN = 4e6;
int n, m, len;
int f[MAXN + 5], g[MAXN + 5];
int Power(int a, int b)
{
	if(b < 0) a = Power(a, P - 2), b = - b;
	int res = 1;
	while(b > 0){
		if(b % 2 == 1) res = res * a % P;
		a = a * a % P;
		b >>= 1;
	}
	return res;
}
void NTT(int * f, int n, int rev)
{
	if(n == 1) return;
	int f1[n / 2 + 1], f2[n / 2 + 1];
	for(int i = 0; i <= n; i += 2){
		f1[i / 2] = f[i];
		f2[i / 2] = f[i + 1];
	}
	NTT(f1, n / 2, rev);
	NTT(f2, n / 2, rev);
	int w = 1, wn = Power(G, rev * (P - 1) / n);
	for(int i = 0; i < n / 2; i ++, w = w * wn % P){
		f[i] = (f1[i] + w * f2[i] % P) % P;
		f[i + n / 2] = (f1[i] - w * f2[i] % P + P) % P;
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 0; i <= n; i ++) scanf("%d", &f[i]);
	for(int i = 0; i <= m; i ++) scanf("%d", &g[i]);
	len = 1 << max((int)ceil(log2(n + m)), 1);
	NTT(f, len, 1);
	NTT(g, len, 1);
	for(int i = 0; i <= len; i ++) f[i] = f[i] * g[i] % P;
	NTT(f, len, - 1);
	for(int i = 0; i <= n + m; i ++) printf("%d ", f[i] * Power(len, - 1) % P);
	putchar('\n');
	return 0;
}

谢谢!

2022/9/5 09:39
加载中...