合肥网站关键词优化公司,注册网站查询系统,众美商务公馆做网站,想建网站做优化题目#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid5730 可以用分治FFT。但自己只写了多项式求逆。 和COGS2259几乎很像。设A(x)#xff0c;指数是长度#xff0c;系数是方案。 \( A(x)^{k} \) 的 m 次项系数表示 k 个连续段组成长度为 m 的序列的方案数。 \( B(x)…题目http://acm.hdu.edu.cn/showproblem.php?pid5730 可以用分治FFT。但自己只写了多项式求逆。 和COGS2259几乎很像。设A(x)指数是长度系数是方案。 \( A(x)^{k} \) 的 m 次项系数表示 k 个连续段组成长度为 m 的序列的方案数。 \( B(x)1F(x)F^{2}(x)F^{3}(x)... \) \( B(x) \frac{1}{1-F(x)} \)通过计算B(x)的逆来看出这个式子 然后多项式求逆就行了。 注意模数 \( 3132^{3}*3*13 \) 原根是10但那个 23 太小了如果 len 大于3的话就会除出小数所以不能直接用NTT 那么就用FFT。FFT不能中途取模所以最大的值是 312×312×100009734400000会让FFT的精度变得很低。所以用拆系数FFT。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define db double
#define ll long long
using namespace std;
const int N1e55,M(118)5,mod313;
const db piacos(-1);
int n,a[M],b[M],tp[M],len,r[M],base;
struct cpl{db x,y;}A[M],B[M],Ta[M],Tb[M],Tc[M],Td[M],Ini,I;
cpl operator (cpl a,cpl b){return (cpl){a.xb.x,a.yb.y};}
cpl operator- (cpl a,cpl b){return (cpl){a.x-b.x,a.y-b.y};}
cpl operator* (cpl a,cpl b){return (cpl){a.x*b.x-a.y*b.y,a.x*b.ya.y*b.x};}
cpl cnj(cpl a){return (cpl){a.x,-a.y};}
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9) retret*10ch-0,chgetchar();return fx?ret:-ret;
}
void upd(int x){xmod?x-mod:0;}
int pw(int x,int k)
{int ret1;while(k){if(k1)ret(ll)ret*x%mod;x(ll)x*x%mod;k1;}return ret;}
void fft(cpl *a,bool fx)
{for(int i1;ilen;i)if(ir[i])swap(a[i],a[r[i]]);for(int R2;Rlen;R1){int mR1;cpl wn(cpl){ cos(pi/m),fx?-sin(pi/m):sin(pi/m) };for(int i0;ilen;iR){cpl wI;for(int j0;jm;j,ww*wn){cpl xa[ij], yw*a[imj];a[ij]xy; a[imj]x-y;}}}if(!fx)return;for(int i0;ilen;i)a[i].x/len,a[i].y/len;
}
void mtt(int n,int *a,int *b,int *c)
{for(len1;lenn1;len1);for(int i0;ilen;i)r[i](r[i1]1)((i1)?len1:0);for(int i0;in;i)A[i](cpl){ a[i]/base,a[i]%base }; for(int in;ilen;i)A[i]Ini;for(int i0;in;i)B[i](cpl){ b[i]/base,b[i]%base }; for(int in;ilen;i)B[i]Ini;fft(A,0); fft(B,0);cpl ta,tb,tc,td;A[len]A[0]; B[len]B[0];for(int i0,jlen;ilen;i,j--){ta(A[i]cnj(A[j]))*(cpl){0.5,0};tb(A[i]-cnj(A[j]))*(cpl){0,-0.5};tc(B[i]cnj(B[j]))*(cpl){0.5,0};td(B[i]-cnj(B[j]))*(cpl){0,-0.5};Ta[i]ta*tc; Tb[i]ta*td; Tc[i]tb*tc; Td[i]tb*td;}A[len]B[len]Ini;for(int i0;ilen;i)A[i]Ta[i]Tb[i]*(cpl){0,1};for(int i0;ilen;i)B[i]Tc[i]Td[i]*(cpl){0,1};fft(A,1); fft(B,1);for(int i0,Da,Db,Dc,Dd;in;i){Da(ll)(A[i].x0.5)%mod; Db(ll)(A[i].y0.5)%mod;Dc(ll)(B[i].x0.5)%mod; Dd(ll)(B[i].y0.5)%mod;c[i](Da*base*base(DbDc)*baseDd)%modmod; upd(c[i]);}
}
void getinv(int n,int *a,int *b)
{if(n1){b[0]pw(a[0],mod-2);return;}getinv(n11,a,b);mtt(n,a,b,tp);mtt(n,tp,b,tp);for(int i0;in;i)b[i]((b[i]1)-tp[i])%modmod,upd(b[i]);
}
int main()
{basesqrt(mod); I.x1;while(1){memset(a,0,sizeof a);memset(b,0,sizeof b);nrdn(); if(!n)return 0;for(int i1;in;i)a[i]rdn();for(int i1;in;i)a[i]mod-a[i]%mod,upd(a[i]);a[0];getinv(n1,a,b);printf(%d\n,b[n]);}return 0;
} 转载于:https://www.cnblogs.com/Narh/p/10056981.html
