迭代优化好像不加也有100分（FFT），并没有T两个点啊...

NTT在FFT的基础上除了模数和wn外还有什么不同吗？或者如何把FFT改为NTT（死活改不对）。

wn=power(3,(P-1)/(1<<n))*op
//op=1 or -1，P=998244353

是这个吗？

还有答案好像要从除以n改为乘 $n^{P-2}$

我的NTT：

WA22分（#2 #3 AC）

#1:

输入：
5 5
1 7 4 0 9 4 
8 8 2 4 5 5 
输出：
8 64 90 50 113 160 105 64 61 65 20 
我的输出：
127008084 465086971 184310225 882121937 206550947 87386296 488447652 632081436 430613923 350470539 922803736

Code:

#include<bits/stdc++.h>
using namespace std;
#define N 4000010
#define P 998244353
#define int long long
int f[N],g[N];
int power(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%P;
        a=a*a%P;
        b>>=1;
    }
    return ans;
}
void NTT(int *a,int n,int op){
    if(!n)return;
    int a0[n],a1[n];
    for(int i=0;i<n;i++){
        a0[i]=a[i<<1];
        a1[i]=a[i<<1|1];
    }
    NTT(a0,n>>1,op);NTT(a1,n>>1,op);
    int wn=power(3,(P-1)/(1<<n))*op,w=1;
    for(int i=0;i<n;i++,w=w*wn%P){
        a[i]=(a0[i]+a1[i]*w%P)%P;
        a[i+n]=(a0[i]-a1[i]*w%P+P)%P;
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<=n;i++)cin>>f[i];
    for(int i=0;i<=m;i++)cin>>g[i];
    for(m+=n,n=1;n<=m;n<<=1);
    NTT(f,n>>1,1);NTT(g,n>>1,1);
    for(int i=0;i<n;i++)f[i]*=g[i],f[i]%=P;
    NTT(f,n>>1,-1);
    int x=power(n,P-2);
    for(int i=0;i<=m;i++)cout<<(f[i]*x%P+P)%P<<" ";
    system("pause");
    return 0;
}

谢谢！！