HDU 5730——Shell Necklace

骑猪看日落 2022-07-19 05:59 104阅读 0赞

题意：

一段长为i的项链有a\[i\]中装饰方法，问长度为n的项链有多少种装饰方式。

思路：

容易推出，dp\[i\]=∑dp\[j\]\*a\[i-j\],(1<=j<=i-1)那么这样就刚好符合卷积的运算，这样就可以愉快地使用fft了，不过数量级在1e5，所以应该采用分治来处理，算法复杂度nlognlogn。

code：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    const double PI=acos(-1.0);
    typedef long long ll;
    
    struct complex
    {
        double l,r;
        complex(double ll=0.0,double rr=0.0){
            l=ll;r=rr;
        }
        complex operator +(const complex& B){
            return complex(l+B.l,r+B.r);
        }
        complex operator - (const complex& B){
            return complex(l-B.l,r-B.r);
        }
        complex operator *(const complex& B){
            return complex(l*B.l-r*B.r,l*B.r+B.l*r);
        }
    };
    
    /* * 进行FFT和IFFT前的反转变换。 * 位置i和j（i二进制反转后位置）互换 * len必须是2的幂 */
    void change(complex y[],int len){
        int i,j,k;
        for (int i=1,j=len/2;i<len-1;i++){
            if (i<j) swap(y[i],y[j]);
            k=len/2;
            while (j>=k){
                j-=k;
                k>>=1;
            }
            if (j<k) j+=k;
        }
    }
    /* * 做FFT * len必须为2^k形式， * on==1时是DFT，on==-1时是IDFT */
    void fft(complex y[],int len,int on){
        change(y,len);
        for (int h=2;h<=len;h<<=1){
            complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
            for (int j=0;j<len;j+=h){
                complex w(1,0);
                for (int k=j;k<j+h/2;k++){
                    complex u=y[k];
                    complex t=w*y[k+h/2];
                    y[k]=u+t;
                    y[k+h/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if (on==-1){
            for (int i=0;i<len;i++){
                y[i].l/=len;
            }
        }
    }
    const int N=1e5+5;
    int n;
    complex x[N<<2],y[N<<2];
    int dp[N],v[N];
    const int mod=313;
    void sol(int l,int r){
        if (l==r) {dp[l]+=v[l];dp[l]%=mod;return;}
        int mid=(l+r)>>1;
        sol(l,mid);
        int len=1;
        while (len<=(r-l+1)) len<<=1;
        for (int i=0;i<len;i++) x[i]=y[i]=complex(0,0);
        for (int i=l;i<=mid;i++) x[i-l]=complex(dp[i],0);
        for (int i=0;i<r-l+1;i++) y[i]=complex(v[i+1],0);
        fft(x,len,1);fft(y,len,1);
        for (int i=0;i<len;i++) x[i]=x[i]*y[i];
        fft(x,len,-1);
        for (int i=mid+1;i<=r;i++)
             dp[i]+=(int)(x[i-l-1].l+0.5),dp[i]%=mod;
        sol(mid+1,r);
    }
    int main()
    {
        while (~scanf("%d",&n),n){
            for (int i=1;i<=n;i++){
                scanf("%d",v+i);
                v[i]%=mod;dp[i]=0;
            }
            sol(1,n);
            printf("%d\n",dp[n]);
        }
    }