A simple Blog for wyx I've been down the bottle hoping.
hdu5730 cdq+FFT
发表于: | 分类: Oi | 评论:0 | 阅读:137

题目大意
给出长度分别为$1~n$的珠子,长度为$i$的珠子有$a_i$种,每种珠子有无限个,问用这些珠子串成长度为$n$的链有多少种方案

大概这个东西就是强行套了一波两个模板233333
首先容易得到$$f(i)=\sum\limits_{j=0}^{i-1}{f(j)*a_{j-i}}$$
然后你发现这个东西直接做是$n^3$
然后你把卷积$FFT$一下,就把一个n变成了$\log$
然而还没结束这才$n^2\log(n)$
我们发现这个东西在算的时候只和前面的东西有关
于是可以把枚举$j$改成按$j$分治
一个$n$变成了$\log$
总的时间复杂度是$n\log^2(n)$
别忘了多组数据的事情

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N =  4e5+5;
const double PI = acos(-1);
const int mod = 313;
using namespace std;

int F[N];
int A[N];

struct cp{
    double a,b;
    cp (double _a=0,double _b=0) :a(_a),b(_b){}
    inline cp operator + (const cp &z)const{
        return cp(a+z.a,b+z.b);
    }
    inline cp operator - (const cp &z)const{
        return cp(a-z.a,b-z.b);
    }
    inline cp operator * (const cp &z)const{
        return cp(a*z.a-b*z.b,a*z.b+b*z.a);
    }
}a[N],b[N],c[N],x,y;

inline void FFT(cp *a,int len,int type){
    register int i, j ,k;
    for(i=0,k=0;i<len;i++) {
        if(k<i) swap(a[i],a[k]);
        for(int j=len>>1;(k^=j)<j;j>>=1);
    }
    for(i=2;i<=len;i<<=1){
        cp wn(cos(2*PI/i),type*sin(2*PI/i));
        for(k=0;k<len;k+=i){
            cp w(1,0);
            for(j=k;j<k+i/2;++j,w=w*wn){
                x = a[j], y = a[j+i/2]*w;
                a[j] = x + y, a[j+i/2] = x - y;
            }
        }
    }
    if(type == -1)  for(i=0;i<len;++i) a[i].a /= len;
}

inline void solve(int L,int R){
    if(L==R){
        F[L] += A[L];
        F[L] %= mod;
        return ;
    }
    register int i;
    int mid = (L+R) >> 1;
    solve(L,mid);
    int len = 1;
    for(;len<=R-L+1;len<<=1);
    for(i=0;i<len;++i) a[i] = b[i] = cp(0,0);
    for(i=L;i<=mid;++i) a[i-L] = cp(F[i]);
    for(i=1;L+i<=R;++i) b[i-1] = cp(A[i]);
    FFT(a,len,1); FFT(b,len,1);
    for(i=0;i<len;++i) c[i] = a[i] * b[i];
    FFT(c,len,-1);
    for(i=mid+1;i<=R;++i){
        F[i] += int(c[i-L-1].a + 0.5);
        F[i] %= mod;
    }
    solve(mid+1,R);
}

inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main(){
    int n ;
    while(cin >> n){
        if(n == 0) return 0;
        memset(F,0,sizeof F);
        for(int i=1;i<=n;++i) A[i] = read()%mod;
        solve(1,n);
        cout << F[n] << endl;
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP