[ctsc2010]性能优化

少见的可做的ctsc题目
少见的我能yy出来的ctsc题目
毕竟是学长出的=_=……还是说点什么吧
→→我是不会贴题解的……


其实看这题之前就被各种大神透一脸……说这是fft……
我在被透后去看了一下题,发现题目是用一个伪代码写的……
好神,这么想着,我关掉了题面
后来就放着了……


最近lz神跟我说我出的那道xxx题可以用这题的方法强化……
我就来看这题了……
读懂题目之后发现这好像是可做题?
这玩意显然有结合律,所以用快速幂就能把c变成lg了,然后我们要计算lgc次循环卷积,看怎么优化吧……
嗯就是让你快速计算循环卷积……
循环卷积……求出模n+1意义下的n次单位根……
弄个多项式求值后每次O(n)的乘法然后……然后再反求不就好了= =
问题是n好像不是啥2的幂次……不过题目保证它的分解式的质因子很小……
那么就还是上fft吧……
fft一般是每次除以2……稍微思考一下也能推广到每次除以c来递归做的吧……
这题就没有了


嘛……毕竟是一道裸题……就这样了……

还是发一下代码吧……
其实在bzoj上的速度是中等偏上?感觉开了O2后某些常数问题被掩盖了
因为不知道数组到底要多大就怒开了一个2000000的数组TAT

中间写傅里叶变换的时候傻了很久……就随便乱写了一个……居然过了……

optimize.cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 2000000
int n,C,p,a[N],inv,w,b[N],trans[N],A[N],primes[4]={2,3,5,7};
inline int mod_pow(int x,int y)
{
    int cur=1;
    for(;y;y>>=1,x=(long long)x*x%p)
        if(y&1)cur=(long long)cur*x%p;
    return cur;
}
inline int proot(){
    static int divisors[50000];
    int i,tot=0;
    for(i=1;i*i<n;i++)
        if(n%i==0)
            divisors[tot++]=i;
    for(;i;i--)
        if(n%i==0)
            divisors[tot++]=n/i;
    for(int x=1;x<=n;x++)
    {
        for(int j=0;j<tot-1;j++)
            if(mod_pow(x,divisors[j])==1)
                goto FAIL;
        return x;
FAIL:;
    }
}void FFT(int*x,int *y,int s,int l)
{
    if(l==1)
        y[s]=x[s];
    else{
        for(int cnt=0;cnt<4;cnt++)
            if(l%primes[cnt]==0){
                int div=primes[cnt];
                for(int i=0;i<div;i++)
                    for(int j=i;j<l;j+=div)
                        y[s+i*(l/div)+j/div]=x[s+j];
                copy(y+s,y+s+l,x+s);
                for(int i=0;i<div;i++)
                    FFT(x,y,s+i*(l/div),l/div);
                int W=mod_pow(w,n/l),POW=mod_pow(W,l/div);
                for(int i=0,z=1;i<div;i++,z=(long long)z*POW%p)
                {
                    for(int j=0,h=z;j<l/div;j++,h=(long long)h*W%p)
                    {
                        x[s+i*(l/div)+j]=0;
                        for(int k=0,tt=1;k<div;k++,tt=(long long)tt*h%p)
                        {
                            x[s+i*(l/div)+j]+=(long long)tt*y[s+k*(l/div)+j]%p;
                            x[s+i*(l/div)+j]%=p;
                        }
                    }
                }copy(x+s,x+s+l,y+s);
                return;
            }
    }
}void DFT(int*x,int *y,int s,int l)
{
    if(l==1)
        y[s]=x[s];
    else{
        for(int cnt=0;cnt<4;cnt++)
            if(l%primes[cnt]==0){
                int div=primes[cnt];
                for(int i=0;i<div;i++)
                    for(int j=i;j<l;j+=div)
                        y[s+i*(l/div)+j/div]=x[s+j];
                copy(y+s,y+s+l,x+s);
                for(int i=0;i<div;i++)
                    DFT(x,y,s+i*(l/div),l/div);
                int W=mod_pow(inv,n/l),POW=mod_pow(W,l/div);
                for(int i=0,z=1;i<div;i++,z=(long long)z*POW%p)
                {
                    for(int j=0,h=z;j<l/div;j++,h=(long long)h*W%p)
                    {
                        x[s+i*(l/div)+j]=0;
                        for(int k=0,tt=1;k<div;k++,tt=(long long)tt*h%p)
                        {
                            x[s+i*(l/div)+j]+=(long long)tt*y[s+k*(l/div)+j]%p;
                            x[s+i*(l/div)+j]%=p;
                        }
                    }
                }copy(x+s,x+s+l,y+s);
                return;
            }
    }
}
int main(){
    scanf("%d%d",&n,&C);p=n+1;w=proot();inv=mod_pow(w,n-1);
    for(int i=0;i<n;i++)scanf("%d",&a[i]),a[i]%=p;
    for(int i=0;i<n;i++)scanf("%d",&b[i]),b[i]%=p;
    FFT(a,A,0,n);FFT(b,trans,0,n);
    C%=n;
    for(int i=0;i<n;i++)
        trans[i]=(long long)mod_pow(trans[i],C)*A[i]%p;
    DFT(trans,a,0,n);
    inv=mod_pow(n,n-1);
    for(int i=0;i<n;i++)
        printf("%d\n",(long long )a[i]*inv%p);
}

Comments

comments powered by Disqus