[CTSC2010]性能优化

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

[CTSC2010]性能优化

循环卷积快速幂

两个注意点：
n+1不是2^k*P+1形式，任意模数又太慢？n=2^k1*3^k2*5^k3*7^k4

多路分治！深刻理解FFT运算本质：分治，推式子得到从下往上的迭代公式

最后求的是w_n^i的点值

快速幂：

循环卷积快速幂比较特殊，就是G*F，>=n的项的系数加到-n位置上

所以，由于w(n,p+n)=w(n,p)，点值相乘直接得到G*F的点值表达

F，B点值，快速幂相乘即可

不用把n扩充系数等。

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define fi first

#define se second

#define mk(a,b) make_pair(a,b)

#define numb (ch^'0')

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}

namespace Miracle{

const int N=5e5+;

int pri[]={,,,};

int n,mod,C;

int G,GI;

int ci[];

int ad(int x,int y){

    return x+y>=mod?x+y-mod:x+y;

}

int qm(int x,int y){

    int ret=;

    while(y){

        if(y&) ret=(ll)ret*x%mod;

        x=(ll)x*x%mod;

        y>>=;

    }

    return ret;

}

int dep[],cnt;

void divi(){

    int tmp=n;

    while(tmp%==) tmp/=,dep[++cnt]=,++ci[];

    while(tmp%==) tmp/=,dep[++cnt]=,++ci[];

    while(tmp%==) tmp/=,dep[++cnt]=,++ci[];

    while(tmp%==) tmp/=,dep[++cnt]=,++ci[];

}

bool che(int x){

    for(reg i=;i<;++i){

        if(ci[pri[i]]){

            if(qm(x,n/pri[i])==) return false;

        }

    }

    return true;

}

void fin(){

    G=;

    while(!che(G)) ++G;

}

int f[N];

int b[N];

int pos[N];

int getpos(int x){

//    cout<<" getpos "<<x<<endl;

    int len=n,l=;

    for(reg i=;i<=cnt;++i){

//        cout<<" i "<<i<<" x "<<x<<" ll "<<l<<endl;

        int be=(x-l)%dep[i],th=(x-l)/dep[i];

        len=len/dep[i];

        x=l+len*be+th;

        l=x-th;

    }

//    cout<<" bac "<<x<<endl;

    return x;

}

int g[N];

int pw[*N][];

int mem[];

void FFT(int *f,int n,int c){

    for(reg i=;i<n;++i) g[i]=f[i];

    for(reg i=;i<n;++i) f[pos[i]]=g[i];

    int las=;

    for(reg i=cnt;i>=;--i){

        int p=dep[i];

        int st=(mod-)/(las*p);

        for(reg l=;l<n;l+=las*p){

            for(reg b=;b<las;++b){

                for(reg j=;j<p;++j){

                    mem[j]=;

                    for(reg i=;i<p;++i){

                        mem[j]=ad(mem[j],(ll)pw[st*(b+j*las)*i][c]*f[l+b+i*las]%mod);

                    }

                }

                for(reg j=;j<p;++j){

                    f[l+b+j*las]=mem[j];

                }

            }

        }

        las*=p;

    }

}

int main(){

    rd(n);rd(C);mod=n+;

    divi();fin();GI=qm(G,mod-);

//    cout<<" G "<<G<<" GI "<<GI<<endl;//

    pw[][]=pw[][]=;

    for(reg i=;i<=*n;++i) pw[i][]=(ll)pw[i-][]*GI%mod,pw[i][]=(ll)pw[i-][]*G%mod;

    for(reg i=;i<n;++i) rd(f[i]),f[i]%=mod;

    for(reg i=;i<n;++i) rd(b[i]),b[i]%=mod;

    for(reg i=;i<n;++i) pos[i]=getpos(i);

//    cout<<" pos "<<endl;

//    prt(pos,0,n-1);

    FFT(f,n,);

//    cout<<" ff "<<endl;

//    prt(f,0,n-1);

    FFT(b,n,);

//    cout<<" bb "<<endl;

//    prt(b,0,n-1);

    for(reg i=;i<n;++i) f[i]=(ll)f[i]*qm(b[i],C)%mod;

    FFT(f,n,);

    for(reg i=;i<n;++i){

        f[i]=(ll)f[i]*qm(n,mod-)%mod;

        printf("%d\n",f[i]);

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/3/19 18:42:47

*/