对于每个点 i i i [ 1 , n ] [1, n] [ 1 , n ]
期望边数#
首先，注意到每个点的期望次数一定相同，所以只算一个点即可。
之后利用几何分布相关定理，成功选到非自身的点的概率为 p = n − 1 n \operatorname{p}=\frac{n-1}{n} p = n n − 1 E = 1 p = n n − 1 \operatorname{E}=\frac{1}{p}=\frac{n}{n-1} E = p 1 = n − 1 n
下面给出证明。
由期望的定义可知，设 p = n − 1 n p=\frac{n-1}{n} p = n n − 1
E = 1 × ( 1 − p ) 0 ⋅ p + 2 × ( 1 − p ) 1 ⋅ p + 3 × ( 1 − p ) 2 ⋅ p + ⋯ + k × ( 1 − p ) k − 1 ⋅ p E=1\times (1-p)^0\cdot p+2\times(1-p)^1\cdot p+3\times(1-p)^2\cdot p+\cdots+k\times (1-p)^{k-1}\cdot p E = 1 × ( 1 − p ) 0 ⋅ p + 2 × ( 1 − p ) 1 ⋅ p + 3 × ( 1 − p ) 2 ⋅ p + ⋯ + k × ( 1 − p ) k − 1 ⋅ p 设 q = 1 − p q=1-p q = 1 − p
E = p ⋅ ( 1 ⋅ q 0 + 2 ⋅ q 1 + 3 ⋅ q 2 + ⋯ + k ⋅ q k − 1 ) E=p\cdot (1\cdot q^0+2\cdot q^1+3\cdot q^2+\cdots + k\cdot q^{k-1}) E = p ⋅ ( 1 ⋅ q 0 + 2 ⋅ q 1 + 3 ⋅ q 2 + ⋯ + k ⋅ q k − 1 ) 设 S = E p S=\frac{E}{p} S = p E
S = 1 ⋅ q 0 + 2 ⋅ q 1 + 3 ⋅ q 2 + ⋯ + k ⋅ q k − 1 q ⋅ S = 0 ⋅ q 0 + 1 ⋅ q 1 + 2 ⋅ q 2 + ⋯ + ( k − 1 ) ⋅ q k − 1 + k ⋅ q k ( 1 − q ) S = q 0 + q 1 + q 2 + q 3 + ⋯ + q k − 1 − k ⋅ q k ( 1 − q ) S = 1 − q k 1 − q − k ⋅ q k \begin{array}{rl}
S&=1\cdot q^0+2\cdot q^1+3\cdot q^2+\cdots + k\cdot q^{k-1}\\
q\cdot S&=\textcolor{white}{0\cdot q^0}+1\cdot q^1+2\cdot q^2+\cdots+(k-1)\cdot q^{k-1}+k\cdot q^k\\
(1-q)S &= q^0+q^1+q^2+q^3+\cdots +q^{k-1}-k\cdot q^k\\
(1-q)S &= \dfrac{1-q^k}{1-q}-k\cdot q^k
\end{array} S q ⋅ S ( 1 − q ) S ( 1 − q ) S = 1 ⋅ q 0 + 2 ⋅ q 1 + 3 ⋅ q 2 + ⋯ + k ⋅ q k − 1 = 0 ⋅ q 0 + 1 ⋅ q 1 + 2 ⋅ q 2 + ⋯ + ( k − 1 ) ⋅ q k − 1 + k ⋅ q k = q 0 + q 1 + q 2 + q 3 + ⋯ + q k − 1 − k ⋅ q k = 1 − q 1 − q k − k ⋅ q k 当 k → + ∞ k\rightarrow +\infty k → + ∞ q k → 0 q^k\rightarrow 0 q k → 0
S = 1 ( 1 − q ) 2 S=\frac{1}{(1-q)^2} S = ( 1 − q ) 2 1 期望为：
E = p ⋅ S = p ( 1 − q ) 2 = 1 p E=p\cdot S=\frac{p}{(1-q)^2}=\frac{1}{p} E = p ⋅ S = ( 1 − q ) 2 p = p 1 共 n n n
Ans = n ⋅ E = n n − 1 n = n 2 n − 1 \operatorname{Ans}=n\cdot E=\frac{n}{\frac{n-1}{n}}=\frac{n^2}{n-1} Ans = n ⋅ E = n n − 1 n = n − 1 n 2 期望连通块数#
如果把每个点向其他点连的边看为有向边，则每个点的出度均为 1 1 1
因此：环的个数 = = = = = = E E E
E = 所有图中环的总数 图的总数 = A B E=\frac{\text{所有图中环的总数}}{\text{图的总数}}=\frac{A}{B} E = 图的总数 所有图中环的总数 = B A 每个点都可以向外连边，图的总数为：
B = ( n − 1 ) n B=(n-1)^n B = ( n − 1 ) n 环的总数：先枚举环的点数 i i i
A = ∑ i = 2 n ( n i ) ⋅ ( n − 1 ) n − i ⋅ ( i − 1 ) ! A=\sum_{i=2}^n \binom{n}{i}\cdot (n-1)^{n-i}\cdot (i-1)! A = i = 2 ∑ n ( i n ) ⋅ ( n − 1 ) n − i ⋅ ( i − 1 )! 化简：
E = A B = ∑ i = 2 n ( n i ) ⋅ ( n − 1 ) n − i ⋅ ( i − 1 ) ! ( n − 1 ) n = ∑ i = 2 n n ! ⋅ ( i − 1 ) ! i ! ⋅ ( n − i ) ! ⋅ ( n − 1 ) i = ∑ i = 2 n n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ ( n − i + 1 ) i ⋅ ( n − 1 ) i \begin{aligned}
E &= \frac{A}{B}\\
&= \sum_{i=2}^n \dfrac{\binom{n}{i}\cdot (n-1)^{n-i}\cdot (i-1)!}{(n-1)^n}\\
&= \sum_{i=2}^n \dfrac{n!\cdot (i-1)!}{i!\cdot (n-i)!\cdot (n-1)^i}\\
&= \sum_{i=2}^n \dfrac{n\cdot (n-1)\cdot (n-2)\cdots(n-i+1)}{i\cdot (n-1)^i}
\end{aligned} E = B A = i = 2 ∑ n ( n − 1 ) n ( i n ) ⋅ ( n − 1 ) n − i ⋅ ( i − 1 )! = i = 2 ∑ n i ! ⋅ ( n − i )! ⋅ ( n − 1 ) i n ! ⋅ ( i − 1 )! = i = 2 ∑ n i ⋅ ( n − 1 ) i n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ ( n − i + 1 ) 不用预处理逆元，可以 O ( n ) \mathcal O(n) O ( n )
#define int long long using namespace std ; const int mod = 998244353 ; int n, ans = 0 ; inline int power ( int x , int k ) { int ret = 1 ; while (k) { if (k & 1 ) ret = ret * x % mod; x = x * x % mod; k >>= 1 ; } return ret; } inline int inv ( int x ) { return power (x, mod - 2 ); } signed main () { cin >> n; printf ( " %lld\n " , n * n % mod * inv (n - 1 ) % mod); int tmp = n, Pow = n - 1 ; for ( int i = 2 ; i <= n; i ++ ) { tmp = tmp * (n - i + 1 ) % mod; Pow = Pow * (n - 1 ) % mod; ans = (ans + tmp * inv (i) % mod * inv (Pow) % mod) % mod; } printf ( " %lld\n " , ans); return 0 ; } cpp