企业网站建设北京,做兼职的网站 知乎,工程承包网站有哪些,江苏建筑模板厂家题意#xff1a;
一段长为i的项链有a[i]中装饰方法#xff0c;问长度为n的项链有多少种装饰方式。
思路#xff1a;
容易推出#xff0c;dp[i]∑dp[j]*a[i-j],(1ji-1)那么这样就刚好符合卷积的运算#xff0c;这样就可以愉快地使用fft了#xff0c;不过数量级…题意
一段长为i的项链有a[i]中装饰方法问长度为n的项链有多少种装饰方式。
思路
容易推出dp[i]∑dp[j]*a[i-j],(1ji-1)那么这样就刚好符合卷积的运算这样就可以愉快地使用fft了不过数量级在1e5所以应该采用分治来处理算法复杂度nlognlogn。
code
#include iostream
#include cstdio
#include cstring
#include cmath
#include algorithm
using namespace std;const double PIacos(-1.0);
typedef long long ll;struct complex
{double l,r;complex(double ll0.0,double rr0.0){lll;rrr;}complex operator (const complex B){return complex(lB.l,rB.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.rB.l*r);}
};/** 进行FFT和IFFT前的反转变换。* 位置i和ji二进制反转后位置互换* len必须是2的幂*/
void change(complex y[],int len){int i,j,k;for (int i1,jlen/2;ilen-1;i){if (ij) swap(y[i],y[j]);klen/2;while (jk){j-k;k1;}if (jk) jk;}
}
/** 做FFT* len必须为2^k形式* on1时是DFTon-1时是IDFT*/
void fft(complex y[],int len,int on){change(y,len);for (int h2;hlen;h1){complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for (int j0;jlen;jh){complex w(1,0);for (int kj;kjh/2;k){complex uy[k];complex tw*y[kh/2];y[k]ut;y[kh/2]u-t;ww*wn;}}}if (on-1){for (int i0;ilen;i){y[i].l/len;}}
}
const int N1e55;
int n;
complex x[N2],y[N2];
int dp[N],v[N];
const int mod313;
void sol(int l,int r){if (lr) {dp[l]v[l];dp[l]%mod;return;}int mid(lr)1;sol(l,mid);int len1;while (len(r-l1)) len1;for (int i0;ilen;i) x[i]y[i]complex(0,0);for (int il;imid;i) x[i-l]complex(dp[i],0);for (int i0;ir-l1;i) y[i]complex(v[i1],0);fft(x,len,1);fft(y,len,1);for (int i0;ilen;i) x[i]x[i]*y[i];fft(x,len,-1);for (int imid1;ir;i)dp[i](int)(x[i-l-1].l0.5),dp[i]%mod;sol(mid1,r);
}
int main()
{while (~scanf(%d,n),n){for (int i1;in;i){scanf(%d,vi);v[i]%mod;dp[i]0;}sol(1,n);printf(%d\n,dp[n]);}
}
