建设银行网站登不上,桂林生活网官方网站,闵行区个人网页设计用户体验,新网站的站点验证传送门
题意#xff1a;求NNN个点的带标号无向连通简单图的个数。 N≤130000N \leq 130000N≤130000
这个问题的主要矛盾在于连通
这个并不好表示#xff0c;但可以用这个表示出不要求连通的方案数
由于带标号#xff0c;先构造答案的EGF f(x)∑i0∞aii!xif(x)\sum_{i0}…传送门
题意求NNN个点的带标号无向连通简单图的个数。
N≤130000N \leq 130000N≤130000
这个问题的主要矛盾在于连通
这个并不好表示但可以用这个表示出不要求连通的方案数
由于带标号先构造答案的EGF f(x)∑i0∞aii!xif(x)\sum_{i0}^\infin\frac{a_i}{i!}x^if(x)∑i0∞i!aixi,其中aia_iai表示iii个点的带标号无向连通简单图的个数。
设EGF g(x)∑i0∞bii!xig(x)\sum_{i0}^\infin\frac{b_i}{i!}x^ig(x)∑i0∞i!bixi表示iii个点的带标号无向连通简单图的个数。
显然bi2Ci2b_i2^{C_i^2}bi2Ci2
然后可以用fff表示ggg:枚举连通块的数量求幂,除以顺序i!i!i!(000是来凑数的)
g(x)∑i0∞fi(x)i!g(x)\sum_{i0}^\infin\frac{f^i(x)}{i!}g(x)i0∑∞i!fi(x)
这是什么exe^xex的泰勒展开式啊泰勒展开在x00x_00x00时称麦克劳林级数
g(x)ef(x)g(x)e^{f(x)}g(x)ef(x)
f(x)ln(g(x))f(x)ln(g(x))f(x)ln(g(x))
求个lnlnln即可
复杂度O(nlogn)O(nlogn)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 262144
using namespace std;
const int MOD1004535809;
typedef long long ll;
int fac[MAXN],finv[MAXN];
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD;p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
int r[MAXN],rt[2][22];
inline void init(const int l){for (int i0;i(1l);i) r[i](r[i1]1)|((i1)(l-1));}
void NTT(int* a,int l,int type)
{int lim1l;for (int i0;ilim;i) if (ir[i]) swap(a[i],a[r[i]]);for (int L0;Ll;L){int mid1L,lenmid1;int Wnrt[type][L1];for (int s0;slim;slen)for (int k0,w1;kmid;k,w(ll)w*Wn%MOD){int xa[sk],y(ll)w*a[smidk]%MOD;a[sk]add(x,y);a[smidk]dec(x,y);}}if (type){int tinv(lim);for (int i0;ilim;i) a[i](ll)a[i]*t%MOD;}
}
void getinv(int* A,int* B,int n)
{static int t[MAXN];if (n1) return (void)(*Binv(*A));getinv(A,B,(n1)1);int l0;while ((1l)(n1)) l;for (int i0;in;i) t[i]A[i];for (int in;i(1l);i) t[i]B[i]0;init(l);NTT(t,l,0);NTT(B,l,0);for (int i0;i(1l);i) B[i](ll)B[i]*(MOD2-(ll)t[i]*B[i]%MOD)%MOD;NTT(B,l,1);for (int in;i(1l);i) B[i]0;
}
inline void deriv(int* A,int* B,int n)
{for (int i0;in-1;i) B[i](ll)A[i1]*(i1)%MOD;B[n-1]0;
}
inline void integ(int* A,int* B,int n)
{for (int i1;in;i) B[i](ll)A[i-1]*finv[i]%MOD*fac[i-1]%MOD;B[0]0;
}
void getln(int* A,int* B,int n)
{static int f[MAXN],g[MAXN];deriv(A,f,n);getinv(A,g,n);int l0;while ((1l)(n1)) l;init(l);for (int in;i(1l);i) f[i]g[i]0;NTT(f,l,0);NTT(g,l,0);for (int i0;i(1l);i) f[i](ll)f[i]*g[i]%MOD;NTT(f,l,1);integ(f,B,n);
}
int f[MAXN],g[MAXN];
int main()
{rt[0][21]qpow(3,479);rt[1][21]inv(rt[0][21]);for (int i20;i0;i--){rt[0][i](ll)rt[0][i1]*rt[0][i1]%MOD;rt[1][i](ll)rt[1][i1]*rt[1][i1]%MOD;}int n;scanf(%d,n);fac[0]1;for (int i1;in;i) fac[i](ll)fac[i-1]*i%MOD;finv[n]inv(fac[n]);for (int in-1;i0;i--) finv[i](ll)finv[i1]*(i1)%MOD;for (int i0;in;i) f[i](ll)qpow(2,((ll)i*(i-1)/2)%(MOD-1))*finv[i]%MOD;getln(f,g,n1);printf(%d\n,(ll)g[n]*fac[n]%MOD);return 0;
}
