\(n\)阶竞赛图，给定\(m\)条链，每条链形似\(x_1,x_2,...,x_k\)，每条边方向为\(x_i\longrightarrow x_{i+1}\)，一个点不会同时存在于两条链。求期望强联通分量个数
若\(m=0\)，强联通分量个数=相邻强联通分量间隔个数\(+1\)
枚举一个强联通分量
\(ans=1+\sum\limits_{i=1}^{n-1}{n\choose i}(\frac{1}{2})^{i(n-i)}\)
对于第\(i\)条链，长度为\(k\)，令\(A_i=1+2x+2x^2+\cdots 2x^{k-1}+x^k\)
对于某点不出现在任意链，令\(A_i=1+x\)
令\(G(x)=\prod A_i\)
\(ans=1+\sum\limits_{i=1}^{n-1}(\frac{1}{2})^{i(n-i)}[x^i]G(x)\)
分治可以做到\(O(nlog^2n)\)
ln手动展开一下，理论\(O(nlogn)\)
原文：https://www.cnblogs.com/Grice/p/12995242.html