网站建设行吗,做网站PPPOE网络可以吗,网站图片搜索技术哪里可以做,快速建站网站正题
题目链接:https://www.luogu.org/problemnew/show/P4841 题目大意
求nnn个点的简单联通无向图的个数。 解题思路
首先考虑n2n^2n2#xff0c;我们设gig_igi表示iii个点的简单无向图的个数#xff0c;显然gi2n(n−1)2g_i2^{\frac{n(n-1)}{2}}gi22n(n−1)
然后我…正题
题目链接:https://www.luogu.org/problemnew/show/P4841 题目大意
求nnn个点的简单联通无向图的个数。 解题思路
首先考虑n2n^2n2我们设gig_igi表示iii个点的简单无向图的个数显然gi2n(n−1)2g_i2^{\frac{n(n-1)}{2}}gi22n(n−1)
然后我们设fif_ifi表示iii个点的简单无向联通图的个数然后我们只要固定一个联通块大小为k(ki)k(ki)k(ki)然后剩下的点都不与其联通就可以去掉不连通的。
也就是fngn−∑i1n−1fi∗Cn−1i−1∗gn−if_ng_n-\sum_{i1}^{n-1}f_i*C_{n-1}^{i-1}*g_{n-i}fngn−i1∑n−1fi∗Cn−1i−1∗gn−i
这就是O(n2)O(n^2)O(n2)
之后我们考虑优化将CCC拆开 fngn−∑i1n−1fi∗(i−1)!(n−i)!(i−1)!∗gn−if_ng_n-\sum_{i1}^{n-1}f_i*\frac{(i-1)!}{(n-i)!(i-1)!}*g_{n-i}fngn−i1∑n−1fi∗(n−i)!(i−1)!(i−1)!∗gn−i 然后将nnn的项提出 fngn−∑i1n−1fi∗(n−1)!(n−i)!(i−1)!∗gn−if_ng_n-\sum_{i1}^{n-1}f_i*\frac{(n-1)!}{(n-i)!(i-1)!}*g_{n-i}fngn−i1∑n−1fi∗(n−i)!(i−1)!(n−1)!∗gn−i gn(n−1)!∑i1nfi(i−1)!gn−i(n−i)!\frac{g_n}{(n-1)!}\sum_{i1}^n\frac{f_i}{(i-1)!}\frac{g_{n-i}}{(n-i)!}(n−1)!gni1∑n(i−1)!fi(n−i)!gn−i 然后使用NTTNTTNTT卷起来 F(x)∑i1∞fi(i−1)!xiF(x)\sum_{i1}^{\infty}\frac{f_i}{(i-1)!}x^iF(x)i1∑∞(i−1)!fixi G(x)∑i0∞gn−i(n−i)!xiG(x)\sum_{i0}^{\infty}\frac{g_{n-i}}{(n-i)!}x^iG(x)i0∑∞(n−i)!gn−ixi H(x)∑n1∞gn(n−1)!xnH(x)\sum_{n1}^{\infty}\frac{g_n}{(n-1)!}x^nH(x)n1∑∞(n−1)!gnxn 上两个的iii与最后一个的nnn同理所以现在有 H(x)F(x)G(x)H(x)F(x)G(x)H(x)F(x)G(x) F(x)H(x)G(x)−1F(x)H(x)G(x)^{-1}F(x)H(x)G(x)−1 现在我们要求F(x)F(x)F(x)而H(x)H(x)H(x)和G(x)G(x)G(x)都知道。
那么我们将G(x)G(x)G(x)进行求逆后用NTTNTTNTT与H(x)H(x)H(x)相乘就好了。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define ll long long
using namespace std;
const ll N131000,XJQ1004535809;
ll n,fac[N],inv[N],r[N*4],Gi;
ll power(ll x,ll b)
{ll ans1;while(b){if(b1) ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
struct Poly{ll x[N*4];void cpy(Poly a,ll len){for(ll i0;ilen;i)x[i]a.x[i];}void reset(ll len){for(ll i0;ilen;i)x[i]0;}void ntt(ll n,ll op){for(ll i1;in;i)r[i](r[i1]1)|((i1)?n1:0);for(ll i0;in;i)if(ir[i])swap(x[i],x[r[i]]);for(ll p2;pn;p1){ll lenp1,tmppower(3,(XJQ-1)/p);if(op-1)tmppower(tmp,XJQ-2);for(ll k0;kn;kp){ll buf1;for(ll ik;iklen;i){ll ttbuf*x[leni]%XJQ;x[leni](x[i]-ttXJQ)%XJQ;x[i](x[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}}
};
Poly get_inv(Poly a,Poly b,Poly c,ll n){if(a.x[0]1) b.x[0]1;else b.x[0]power(a.x[0],XJQ-2);for(ll w1;(1(w-1))n;w){ll len(1w);c.cpy(a,len);c.ntt(len*2,1);b.ntt(len*2,1);for(ll i0;i(len1);i)b.x[i](2-b.x[i]*c.x[i]%XJQXJQ)*b.x[i]%XJQ;b.ntt(len*2,-1);ll invpower(len*2,XJQ-2);for(ll i0;ilen;i)b.x[i]b.x[i]*inv%XJQ;for(ll ilen;ilen*2;i) b.x[i]0;}return b;
}
Poly H,Ginv,a,b;
int main()
{scanf(%lld,n);n;fac[0]fac[1]inv[0]inv[1]1;for(ll i2;in;i){inv[i]XJQ-(XJQ/i)*inv[XJQ%i]%XJQ;fac[i]fac[i-1]*inv[i]%XJQ;}Ginv.x[0]1;for(ll i1;in;i){ll tmppower(2,i*(i-1)/2%(XJQ-1));H.x[i]tmp*fac[i-1]%XJQ,Ginv.x[i]tmp*fac[i]%XJQ;}Ginvget_inv(Ginv,a,b,n);ll len1,w0;while(len(n1)) len1,w;for(ll in;ilen;i) Ginv.x[i]0;H.ntt(len,1);Ginv.ntt(len,1);for(ll i0;ilen;i)H.x[i]H.x[i]*Ginv.x[i]%XJQ;H.ntt(len,-1);printf(%lld,power(inv[2],w)*H.x[n-1]%XJQ*power(fac[n-2],XJQ-2)%XJQ);
}
