RT,样例输出全是 0,求大佬帮忙调一下,应该码风还可以看。
#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;
}
谢谢!