Shell Necklace (dp递推改cdq分治 + fft)

发布时间：2020-12-15 23:24:43 所属栏目：安全来源：网络整理

导读：首先读出题意，然后发现这是一道DP，我们可以获得递推式为然后就知道，不行啊，时间复杂度为O(n 2 ),然后又可以根据递推式看出这里面可以拆解成多项式乘法，但是即使用了fft，我们还需要做n次多项式乘法，时间复杂度又变成O(n 2 * log n)，显然不可以。然后

首先读出题意，然后发现这是一道DP，我们可以获得递推式为

然后就知道，不行啊，时间复杂度为O(n²),然后又可以根据递推式看出这里面可以拆解成多项式乘法，但是即使用了fft，我们还需要做n次多项式乘法，时间复杂度又变成O(n² * log n)，显然不可以。然后又利用c分治思维吧问题进行拆分问题但是，前面求出来的结果对后面的结果会产生影响，所以我们使用cdq分治思想来解决这个问题，时间复杂度变为O(n * log²n)。

#include<bits/stdc++.h>
using namespace std;

const double pi = acos(-1.0);
const int mod = 313;
const int maxn = 4e5 + 7;
int in[maxn],dp[maxn];

struct Complex{
    double r,i;
    Complex(double r = 0.0,double i = 0.0):r(r),i(i){};
    Complex operator+(const Complex &rhs){
        return Complex(r + rhs.r,i + rhs.i);
    }
    Complex operator-(const Complex &rhs){
        return Complex(r - rhs.r,i - rhs.i);
    }
    Complex operator*(const Complex & rhs){
        return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r * rhs.i);
    }
}x1[maxn],x2[maxn];

void rader(Complex *F,int len){
    int j = len >> 1;
    for(int i = 1,j = len/2; i < len - 1; i ++){
        if(i < j)swap(F[i],F[j]);
        int k = len / 2;
        while(j >= k){
            j -= k; k /= 2;
        }
        if(j < k) j += k;
    }
}

void FFT(Complex *F,int len,int t){
    rader(F,len);
    for(int h = 2; h <= len; h <<= 1){
        Complex wn(cos(-t*2*pi/h),sin(-t*2*pi/h));
        for(int j = 0; j < len; j += h){
            Complex E(1,0);
            for(int k = j; k < j + h/2; k ++){
                Complex u = F[k];
                Complex v = E * F[k + h/2];
                F[k] = u + v;
                F[k + h/2] = u - v;
                E = E * wn;
            }
        }
    }
    if(t == -1)
        for(int i = 0; i < len; i ++)
        F[i].r /= len;
}

void cdq(int l,int r){
    if(l == r){
        dp[l] = (in[l]+dp[l])%mod;
        return ;
    }
    int m = l + r>>1;
    cdq(l,m);
    int len1 = r - l + 1;
    int len2 = m - l + 1;
    int len = 1;while(len < (len1 + len2)) len <<= 1;
    for(int i = 0; i < len; i ++) x1[i] = x2[i] = Complex(0,0);
    for(int i = 0; i < len2; i ++) x1[i] = Complex(dp[i + l],0);
    for(int i = 0; i < len1; i ++) x2[i] = Complex(in[i],0);
    FFT(x1,len,1);FFT(x2,1);

    for(int i = 0; i < len; i ++) x1[i] = x1[i] * x2[i];
    FFT(x1,-1);
    for(int i = m + 1; i <= r; i ++) dp[i] = (dp[i] + (int)(x1[i - l].r + 0.5)) % mod;
    cdq(m + 1,r);
}

int main(){
    int n;
    while(~scanf("%d",&n),n){
        for(int i = 1; i <= n; i ++){
            scanf("%d",&in[i]);
            in[i] %= mod;
        }
        memset(dp,0,sizeof(dp));
        cdq(1,n);
        printf("%dn",dp[n] % mod);
        for(int i = 0; i <= n; i ++)printf("%d ",dp[i]);printf("n");
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!