M_sea

HDU5730 Shell Necklace
HDU分析设$f[i]$表示前$i$位的方案数。然后显然有$\large f[i]=\sum\limits_{j=...
扫描右侧二维码阅读全文
29
2019/01

HDU5730 Shell Necklace

HDU

分析

设$f[i]$表示前$i$位的方案数。

然后显然有$\large f[i]=\sum\limits_{j=1}^{i-1}f[j]\cdot a[i-j]$。

如果你做过【模板】分治FFT,那这就是板子题了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=400000+10;
const int MOD=313;
const double PI=acos(-1.0);

struct Complex {
    double r,i;
    Complex(double r_=0,double i_=0) { this->r=r_,this->i=i_; }
    Complex operator +(const Complex& x) { return Complex(r+x.r,i+x.i); }
    Complex operator -(const Complex& x) { return Complex(r-x.r,i-x.i); }
    Complex operator *(const Complex& x) { return Complex(r*x.r-i*x.i,r*x.i+i*x.r); }
};

int r[MAXN];
int f[MAXN],g[MAXN];
Complex A[MAXN],B[MAXN];

inline void FFT(Complex* a,int n,int op) {
    for (re int i=0;i<n;++i)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        Complex rot(cos(PI/i),op*sin(PI/i));
        for (re int j=0;j<n;j+=i<<1) {
            Complex w(1,0);
            for (re int k=0;k<i;++k,w=w*rot) {
                Complex x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if (op==-1)
        for (re int i=0;i<n;++i) a[i].r=a[i].r/n+0.5;
}

inline void Mul(Complex* A,Complex* B,int n,int m) {
    int len=1,l=0;
    for (;len<=n+m;len<<=1,++l);
    for (re int i=n;i<len;++i) A[i].r=A[i].i=0;
    for (re int i=m;i<len;++i) B[i].r=B[i].i=0;
    for (re int i=0;i<len;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    FFT(A,len,1),FFT(B,len,1);
    for (re int i=0;i<len;++i) A[i]=A[i]*B[i];
    FFT(A,len,-1);
}

inline void solve(int l,int r) {
    if (l==r) { f[l]=(f[l]+g[l])%MOD; return; }
    int mid=(l+r)>>1;
    solve(l,mid);
    for (re int i=l;i<=mid;++i) A[i-l].r=f[i],A[i-l].i=0;
    for (re int i=1;i<=r-l;++i) B[i-1].r=g[i],B[i-1].i=0;
    Mul(A,B,mid-l+1,r-l);
    for (re int i=mid+1;i<=r;++i) f[i]=(f[i]+(int)A[i-l-1].r)%MOD;
    solve(mid+1,r);
}

int main() {
    while (233) {
        int n=read(); if (!n) break;
        memset(f,0,sizeof(f)); f[0]=1;
        for (re int i=1;i<=n;++i) g[i]=read()%MOD;
        solve(1,n);
        printf("%d\n",f[n]);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 06 PM

发表评论