洛谷 – P7474 -「C.E.L.U-02」学术精神

题意

对于每个点 $i$ 随机与 $[1, n]$ 中的一点连无向边,若连向自己,则保留该边并再次连边,一直重复至连到别的点上为止,求边数与连通块个数期望。

题解

期望边数

首先,注意到每个点的期望次数一定相同,所以只算一个点即可。

之后利用几何分布相关定理,成功选到非自身的点的概率为 $\operatorname{p}=\frac{n-1}{n}$,期望 $\operatorname{E}=\frac{1}{p}=\frac{n}{n-1}$.

下面给出证明。

由期望的定义可知,设 $p=\frac{n-1}{n}$,期望的计算式为:

$$
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
$$

设 $q=1-p$,则:

$$
E=p\cdot (1\cdot q^0+2\cdot q^1+3\cdot q^2+\cdots + k\cdot q^{k-1})
$$

设 $S=\frac{E}{p}$,错位相减求和:

$$
\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}
$$

当 $k\rightarrow +\infty$ 时,$q^k\rightarrow 0$,所以:

$$
S=\frac{1}{(1-q)^2}
$$

期望为:

$$
E=p\cdot S=\frac{p}{(1-q)^2}=\frac{1}{p}
$$

共 $n$ 个点,所以题目所求答案为:

$$
\operatorname{Ans}=n\cdot E=\frac{n}{\frac{n-1}{n}}=\frac{n^2}{n-1}
$$

期望连通块数

如果把每个点向其他点连的边看为有向边,则每个点的出度均为 $1$,所以每个连通块都是基环树。

因此:环的个数 $=$ 基环树个数 $=$ 连通块个数,下面求环的期望数量 $E$.

$$
E=\frac{\text{所有图中环的总数}}{\text{图的总数}}=\frac{A}{B}
$$

每个点都可以向外连边,图的总数为:

$$
B=(n-1)^n
$$

环的总数:先枚举环的点数 $i$,再确定哪些点在环上,其余点可以随便连边,环上的点再圆排列。

$$
A=\sum_{i=2}^n \binom{n}{i}\cdot (n-1)^{n-i}\cdot (i-1)!
$$

化简:

$$
\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}
$$

不用预处理逆元,可以 $\mathcal 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;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇