萌新调自闭了QAQ,多项式exp求助qwq
  • 板块学术版
  • 楼主Deepth
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/20 21:24
  • 上次更新2023/11/3 08:33:39
查看原帖
萌新调自闭了QAQ,多项式exp求助qwq
788123
Deepth楼主2023/7/20 21:24

为什么多项式exp必须要写道4*len啊,换成注释掉那行就会错。。(0_0)

#include <bits/stdc++.h>
#define int long long
#define db long double
#define toint(p) ((int)(p>0?p+0.5:p-0.5))
using namespace std;
const int N = 3e5+10,P=998244353;
const long double pi=acos(-1);
#define out(a) {for(int __=0; __<16;__++)print((a)[__]);cout<<"\n";}
template<typename T>void print(T x){cout<<x<<" ";}
int read(){
    static int fu,num;
    static char ch;
    fu=1,num=0;
    while(!isdigit(ch)){
        if(ch=='-')fu=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return fu*num;
}
int ppow(int x,int n){
    int ans=1;
    for(;n;x=x*x%P,n>>=1)if(n&1)ans=ans*x%P;
    return ans;
}
int n,m,len;
int rev[N];
int invs[N];
struct poly{
    int a[N];
    const static int g=3,gi=332748118;
    int& operator[](int p){return a[p];}
    static int init(int n){
        int k=0;n--;
        for(;n;k++,n>>=1);
        n=1<<k;
        for(int i=0;i<n;i++){
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
        }
        return n;
    }
    void ntt(int op,int len){
        for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
        for(int i=1;i<len;i<<=1){
            int wn=ppow(op==1?g:gi,(P-1)/i/2);
            for(int j=0;j<len;j+=2*i){
                int w=1;
                for(int k=j;k<j+i;k++,w=w*wn%P){
                    int x=a[k],y=a[k+i]*w%P;
                    a[k]=(x+y)%P;a[k+i]=(x-y+P)%P;
                }
            }
        }
        if(op==-1){
            const int inv=ppow(len,P-2);
            for(int i=0;i<len;i++)a[i]=a[i]*inv%P;
        }
    }
    void inv(poly& b,int len){
        memset(b.a,0,sizeof(b.a));
        b[0]=ppow(a[0],P-2);
        poly *F0=&b,*F1=new poly,*mul=new poly;
        memset(F1,0,sizeof(poly));
        for(int i=2;i<2*len;i<<=1){
            init(i*2);
            for(int j=0;j<i;j++)mul->a[j]=a[j];
            for(int j=i/2;j<i;j++)F0->a[j]=0;
            mul->ntt(1,i*2);F0->ntt(1,i*2);
            for(int j=0;j<i*2;j++)F1->a[j]=((2*(F0->a[j])-(F0->a[j])*(F0->a[j])%P*(mul->a[j]))%P+P)%P;
            F1->ntt(-1,i*2);
            swap(F0,F1);
        }
        for(int i=0;i<len;i++)b[i]=F0->a[i];
        for(int i=len;i<len*2;i++)b[i]=0;
    }
    void dao(int len){
        for(int i=1;i<len;i++){
            a[i-1]=i*a[i]%P;
        }a[len]=0;
    }
    void ji(int len){
        invs[1]=1;
        for(int i=2;i<len;i++)
            invs[i]=(-invs[P%i]*(P/i)%P+P)%P;
        for(int i=len-1;i>0;i--){
            a[i]=a[i-1]*invs[i]%P;
        }a[0]=0;
    }
    void ln(poly& b,int len){
        memset(b.a,0,sizeof(b.a));
        len=init(len);
        auto c=new poly;
        for(int i=0;i<len;i++)(*c)[i]=a[i];
        c->inv(b,len);
        c->dao(len);
        init(len*2);
        b.ntt(1,len*2);c->ntt(1,len*2);
        for(int i=0;i<len*2;i++)b[i]=b[i]*(*c)[i]%P;
        b.ntt(-1,len*2);
        b.ji(len);
        for(int i=len;i<len*2;i++)b[i]=0;
    }
    void exp(poly& b,int len){
        memset(b.a,0,sizeof(b.a));
        b[0]=1;
        poly *F0=&b,*F1=new poly,*lnf=new poly;
        memset(F1,0,sizeof(poly));

        // for(int i=2;i<2*len;i<<=1){
        for(int i=2;i<4*len;i<<=1){
            F0->ln(*lnf,i/2);
            for(int j=0;j<i;j++)lnf->a[j]=a[j]-lnf->a[j];
            lnf->a[0]+=1;
            init(2*i);
            lnf->ntt(1,i*2);F0->ntt(1,i*2);
            for(int j=0;j<i*2;j++)F1->a[j]=lnf->a[j]*F0->a[j]%P;
            F1->ntt(-1,i*2);
            swap(F0,F1);
        }
        for(int i=0;i<len;i++)b[i]=F0->a[i];
        for(int i=len;i<len*2;i++)b[i]=0;
    }
}a,b;
int k;
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    a.exp(b,n);
    for(int i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
}```
2023/7/20 21:24
加载中...