MnZn 刚学 NTT 求助分治 FFT
查看原帖
MnZn 刚学 NTT 求助分治 FFT
826774
Little_Fox_Fairy楼主2025/1/22 18:40
#include<bits/stdc++.h>
// #define int long long 
using namespace std;
const int N=4e5+10;
const int mod=998244353;
const int g=3;

int n,m,G,a[N],rev[N];
inline int qpow(int x,int y) {
    int res=1;
    while (y) {
        if (y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return res;
}
inline void NTT(int len,int *a,bool op) {
    for (int i=0;i<len;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=2;k<=len;k<<=1) {
        int siz=k>>1,gen=qpow(op?g:G,(mod-1)/k);
        for (int i=0;i<len;i+=k) {
            int p=1;
            for (int l=i;l<i+siz;l++) {
                int tmp=1ll*a[l+siz]*p%mod;
                a[l+siz]=(a[l]-tmp+mod)%mod;
                a[l]=(a[l]+tmp)%mod;
                p=1ll*p*gen%mod;
            }
        }
    }
    if (op) return ;
    int inv=qpow(len,mod-2);
    for (int i=0;i<len;i++) a[i]=(1ll*a[i]*inv%mod+mod)%mod;
    return ; 
}
int tmp[N];
inline void solve(int *F,int *G,int n) {
    if (n==1) {
        G[0]=qpow(F[0],mod-2);
        return ;
    }
    solve(F,G,(n+1)>>1);
    int len=1;while (len<=n+n) len<<=1;
    for (int i=1;i<len;i++) rev[i]=((rev[i>>1]>>1)|((i&1)?len>>1:0));
    for (int i=0;i<n;i++) tmp[i]=F[i];
    for (int i=n;i<len;i++) tmp[i]=0;
    NTT(len,tmp,1),NTT(len,G,1);
    for (int i=0;i<len;i++) G[i]=(2ll-1ll*G[i]*tmp[i]%mod+mod)%mod*G[i]%mod;
    NTT(len,G,0);
    for (int i=n;i<len;i++) G[i]=0;
    return ;
}
int b[N];
signed main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;a[0]=1;G=qpow(g,mod-2);
    for (int i=1;i<n;i++) cin>>a[i],a[i]=(1-a[i]+mod)%mod;
    solve(a,b,n);
    for (int i=0;i<n;i++) cout<<b[i]<<" ";
    return (0-0);
}
2025/1/22 18:40
加载中...