HDU5730 Shell Necklace
题目大意
已知连续i(1<=i<=n)个贝壳组合成一段项链的方案数a[i],求组合成包含n个贝壳的项链的总方案数。
Solution
- cdq分治
我们考虑最朴素的\(dp\).
设\(f_i\)表示包含\(i\)个贝壳的方案数,很容易写出转移方程:
\(f_i=\sum_{j=1}^if_{i-j}×a_j\)
发现这个dp方程直接转移是\(O(n^2)\)的,要优化一下....
这个式子不就是分治FFT的式子?
直接cdq不就好了吗?
- 多项式求逆
考虑这个东西怎么求逆对吧.
生成函数构出来直接就可以求式子了...(坑+1)
代码实现
分治FFT
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
int f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
const int N=1000010,Mod=313;
const double Pi=acos(-1.0);
int a[N],dp[N],n;
struct node
{
double x,y;
node operator+(const node b)const{return (node){x+b.x,y+b.y};}
node operator-(const node b)const{return (node){x-b.x,y-b.y};}
node operator*(const node b)const{return (node){x*b.x-y*b.y,x*b.y+y*b.x};}
}A[N],B[N];
int r[N],limit;
void FFT(node *A,int type)
{
for(int i=0;i<limit;i++)
if(i<r[i])swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1)
{
node Root=(node){cos(Pi/mid),type*sin(Pi/mid)};
for(int R=mid<<1,j=0;j<limit;j+=R)
{
node Mi=(node){1,0};
for(int k=0;k<mid;k++,Mi=Mi*Root)
{
node X=A[j+k],Y=Mi*A[j+mid+k];
A[j+k]=X+Y;
A[j+mid+k]=X-Y;
}
}
}
}
void cdq(int l,int R)
{
if(l==R)
{
dp[l]=(dp[l]+a[l])%Mod;
return;
}
int mid=(l+R)>>1;
cdq(l,mid);
limit=1;int L=0,len=R-l+1;
while(limit<=len)limit<<=1,L++;
for(int i=0;i<limit;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
for(int i=0;i<limit;i++)A[i].x=B[i].x=0,A[i].y=B[i].y=0;
for(int i=l;i<=mid;i++)A[i-l].x=dp[i],A[i].y=0;
for(int j=1;j+l<=R;j++)B[j-1].x=a[j],B[j-1].y=0;
for(int i=mid-l+1;i<=R-l;i++)
A[i].x=0,A[i].y=0;
for(int i=len;i<limit;i++){
A[i].x=0;A[i].y=0;
B[i].x=0;B[i].y=0;
}
FFT(A,1);FFT(B,1);
for(int i=0;i<limit;i++)
A[i]=A[i]*B[i];
FFT(A,-1);
for(int i=0;i<limit;i++)
A[i].x=A[i].x/limit;
for(int i=mid+1;i<=R;i++)
{
dp[i]+=((ll)(A[i-l-1].x+0.5))%313;
dp[i]%=313;
}
cdq(mid+1,R);
}
int main()
{
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++)a[i]=gi()%Mod;
memset(dp,0,sizeof(dp));
cdq(1,n);
printf("%d\n",dp[n]);
}
return 0;
}
多项式求逆
挖坑待补