青岛网站设计制作,北京网站建设官网,如何创建网站快捷方式到桌面,西安搬家公司正题
题目链接:https://www.luogu.com.cn/problem/P3784 题目大意
你若干个在[1,n][1,n][1,n]的不同数字组成序列aaa。
记录f(x)f(x)f(x)表示将xxx无序拆分成aaa中数字的和的方案数#xff08;一个数字可以使用多次#xff09;。
现在给出所有的f(x)%p(x∈[1,n])f(x)\%p\…正题
题目链接:https://www.luogu.com.cn/problem/P3784 题目大意
你若干个在[1,n][1,n][1,n]的不同数字组成序列aaa。
记录f(x)f(x)f(x)表示将xxx无序拆分成aaa中数字的和的方案数一个数字可以使用多次。
现在给出所有的f(x)%p(x∈[1,n])f(x)\%p\ (x\in[1,n])f(x)%p (x∈[1,n])要求构造一组字典序最小的aaa满足这个条件。
n≤218,p∈[106,230)∩Prin\leq 2^{18},p\in[10^6,2^{30})\cap Prin≤218,p∈[106,230)∩Pri 解题思路
先考虑给出aaa怎么求fff考虑使用生成函数对于一个数字aaa可以表示成11−xa\frac{1}{1-x^{a}}1−xa1 F(x)∑i0nf(i)xi∏i1n11−xaiF(x)\sum_{i0}^nf(i)x^i\prod_{i1}^n\frac{1}{1-x^{a_i}}F(x)i0∑nf(i)xii1∏n1−xai1 lnF(x)∑i1nln11−xai\ln F(x)\sum_{i1}^n\ln\frac{1}{1-x^{a_i}}lnF(x)i1∑nln1−xai1 x(lnF(x))′∑i1naixai1−xaix(\ \ln F(x)\ )\sum_{i1}^n\frac{a_ix^{a_i}}{1-x^{a_i}}x( lnF(x) )′i1∑n1−xaiaixai x(lnF(x))′∑i1n∑j1∞aixijx(\ \ln F(x)\ )\sum_{i1}^n\sum_{j1}^{\infty}a_ix^{ij}x( lnF(x) )′i1∑nj1∑∞aixij 如果我们求出x(lnF(x))′x(\ \ln F(x)\ )x( lnF(x) )′就可以莫反得到每一个aia_iai是否有了。
因为模数很丑所以要用任意模数。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includecmath
#define ll long long
using namespace std;
const ll N120,T115;
const double Piacos(-1);
struct complex{double x,y;complex(double xx0,double yy0){xxx;yyy;return;}
}A[N],B[N],C[N],D[N],E[N],J[N],I[N],w[N];
struct Poly{ll a[N],n;
}F,G,t1;
ll n,P,cnt,pri[N/10],r[N],g[N],f[N],mu[N];
bool v[N];
complex operator(const complex x,const complex y)
{return complex(x.xy.x,x.yy.y);}
complex operator-(const complex x,const complex y)
{return complex(x.x-y.x,x.y-y.y);}
complex operator*(const complex x,const complex y)
{return complex(x.x*y.x-x.y*y.y,x.x*y.yx.y*y.x);}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void FFT(complex *f,ll n,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll lenp1;for(ll k0;kn;kp)for(ll ik;iklen;i){complex tmpw[n/len*(i-k)];if(op-1)tmp.y-tmp.y;complex ttf[ilen]*tmp;f[ilen]f[i]-tt;f[i]f[i]tt;}}if(op-1){for(ll i0;in;i)f[i]complex(f[i].x/n0.5);}return;
}
void Mul(Poly F,Poly G,Poly H){ll l1;while(lF.nG.n-1)l1;for(ll i0;il;i)r[i]r[i1]1|((i1)?(l1):0);for(ll k1;kl;k1)for(ll i0;ik;i)w[l/k*i]complex(cos(Pi/k*i),sin(Pi/k*i));for(ll i0;iF.n;i)A[i]complex(F.a[i]/T,0),B[i]complex(F.a[i]%T,0);for(ll i0;iG.n;i)C[i]complex(G.a[i]/T,0),D[i]complex(G.a[i]%T,0);for(ll iF.n;il;i)A[i]B[i]complex(0,0);for(ll iG.n;il;i)C[i]D[i]complex(0,0);for(ll i0;il;i)E[i]J[i]I[i]complex(0,0);FFT(A,l,1);FFT(B,l,1);FFT(C,l,1);FFT(D,l,1);for(ll i0;il;i){E[i]A[i]*C[i];J[i]A[i]*D[i]C[i]*B[i];I[i]B[i]*D[i];}FFT(E,l,-1);FFT(J,l,-1);FFT(I,l,-1);for(ll i0;il;i){H.a[i](ll)E[i].x*T%P*T%P;(H.a[i](ll)J[i].x*T%P)%P;(H.a[i](ll)I[i].x)%P;}H.nF.nG.n-1;return;
}
void CalcInv(ll n,Poly F,Poly G){if(n1){G.a[0]power(F.a[0],P-2);G.n1;return;}CalcInv(n1,F,G);Mul(G,G,t1);t1.nn;ll pnF.n;F.nn;Mul(t1,F,t1);t1.nn;F.npn;for(ll i0;iG.n;i)G.a[i](2ll*G.a[i]-t1.a[i]P)%P;for(ll iG.n;in;i)G.a[i]P-t1.a[i];G.nn;return;
}
void GetInv(Poly F,Poly G){ll l1;while(lF.n)l1;CalcInv(l,F,G);G.nF.n;return;
}
void GetD(Poly F){for(ll i0;iF.n-1;i)F.a[i]F.a[i1]*(i1)%P;F.n--;return;
}
void GetJ(Poly F){for(ll iF.n;i0;i--)F.a[i]F.a[i-1]*power(i,P-2)%P;F.a[0]0;F.n;return;
}
void GetLn(Poly F){GetInv(F,G);GetD(F);Mul(F,G,F);GetJ(F);return;
}
void Prime(ll n){mu[1]1;for(ll i2;in;i){if(!v[i])pri[cnt]i,mu[i]-1;for(ll j1;jcnti*pri[j]n;j){v[i*pri[j]]1;if(i%pri[j]0)break;mu[i*pri[j]]-mu[i];}}return;
}
signed main()
{scanf(%lld%lld,n,P);for(ll i1;in;i)scanf(%lld,F.a[i]);F.nn1;F.a[0]1;GetLn(F);GetD(F);Prime(n);for(ll i1;in;i)f[i]F.a[i-1];for(ll i1;in;i)for(ll ji;jn;ji)(g[j]f[i]*mu[j/i]P)%P;ll ans0;for(ll i1;in;i)if(g[i])ans;printf(%lld\n,ans);for(ll i1;in;i)if(g[i])printf(%lld ,i);return 0;
}
