求助多项式
查看原帖
求助多项式
455558
Imiya楼主2023/4/26 17:35
#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=3000100,P=998244353,g=3;
namespace ntt{
    inline int fpow(int a,int b){
        int c=1;
        for(;b;b>>=1,a=a*a%P)if(b&1)c=c*a%P;
        return c;
    }
    int flip[N],w[N];
    inline void NTT(int F[],int n){
        for(int i=1;i<n;i++)flip[i]=flip[i>>1]>>1|((n>>1)*(i&1));
        for(int i=0;i<n;i++)if(i<flip[i])swap(F[i],F[flip[i]]);
        for(int i=0;i<n;i++)w[i]=fpow(g,(P-1)/n*i);
        for(int i=2;i<=n;i<<=1){
            for(int j=0;j<n;j+=i){
                for(int k=0;k<(i>>1);k++){
                    int A=(F[j+k]+w[n/i*k]*F[j+k+(i>>1)]%P)%P;
                    int B=(F[j+k]+w[n/i*(k+(i>>1))]*F[j+k+(i>>1)]%P)%P;
                    F[j+k]=A;
                    F[j+k+(i>>1)]=B;
                }
            }
        }
    }
    inline void iNTT(int F[],int n){
        NTT(F,n);
        int invn=fpow(n,P-2);
        for(int i=1;i<(n>>1);i++)swap(F[i],F[n-i]);
        for(int i=0;i<n;i++)F[i]=F[i]*invn%P;
    }
}
using ntt::fpow;
using ntt::NTT;
using ntt::iNTT;
int F[N],F0[N],A[N],n;
int T1[N],T2[N];
signed main(){
//    freopen("read.in","r",stdin);
    cin>>n;
    for(int i=0;i<n;i++)cin>>A[i];
    F0[0]=F[0]=fpow(A[0],P-2);
    for(int i=2;i<=(n*2);i<<=1){
        memcpy(T1,A,i*2*sizeof(A[0]));
        memcpy(T2,F0,i*2*sizeof(F0[0]));
        NTT(T1,i*2);
        NTT(T2,i*2);
        for(int j=0;j<i*2;j++)F[j]=((2*T2[j]-T2[j]*T2[j]%P*T1[j]%P)%P+P)%P;
        iNTT(F,i*2);
        memcpy(F0,F,i*sizeof(F[0]));
    }
    for(int i=0;i<n;i++)cout<<F[i]<<' ';
    return 0;
}

能且只能过样例 qwq

2023/4/26 17:35
加载中...