Luogu P7474 學術精神

題目

對于每個點 $ i $ 随機與 $ [1,n] $ 中的一點連無向邊，若連向自己，則保留該邊并再次連邊，一直重複至連到别的點上為止，求邊數與連通塊個數期望。

思路

來惡補一下機率期望

第一問

一個點連向其他點的機率為 \(\frac{n - 1}{n}\) ，是以期望 \(\frac{n}{n - 1}\) 次即可完成連邊。

一共有 \(n\) 個點，是以第一問的答案就是 \(\frac{n \times n}{n - 1}\)。

第二問

這裡有一個結論就是在本題條件下，對于每一個确定的圖，圖的聯通塊數與其所含環的數量相等。那麼我們隻需要計算出在所有的圖中總共有多少環，再除以圖的數量，那麼就是最後的答案了。

令環的總數為 \(sum\) ，圖的總數為 \(num\) 。

則有

\[num=(n-1)^n

\]

\[Sum=\sum_{i=2}^{n} \times C_{n}^{i} \times(i-1)! \times(n-1)^{n-i}

解釋一下 \(sum\) 的含義，首先我們先确定環的大小 \(i\) ，然後從 \(n\)個點中選擇 \(i\) 個成環，可以形成環的種類是 \((i-1)!\)（圓排列），其餘點随便連邊，最後對其求和（每個确定的環在多少圖中出現過）。因為 \(\Sigma\) (所有的圖中有多少環)與 \(\Sigma\) (每個确定的環在多少圖中出現過)在數值上是等價的，是以可以進行如上計算。

code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10010
#define M 1010
#define ll long long

using namespace std;
const int mod = 998244353;
int n, fac[N];

int read() {
  int s = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
  return f ? -s : s;
}

int q_pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (1ll * ans * a) % mod;
    a = (1ll * a * a) % mod;
    b >>= 1;
  }
  return ans;
}

int C(int n, int m) {
  return 1ll * fac[n] * q_pow(1ll * fac[m] * fac[n - m] % mod, mod - 2) % mod;
}

int main() {
  n = read();
  fac[1] = fac[0] = 1;
  for (int i = 2; i <= n; i++) fac[i] = (1ll * fac[i - 1] * i) % mod;
  cout << 1ll * n * n % mod * q_pow(n - 1, mod - 2) % mod << "\n";
  int sum = 0;
  for (int i = 2; i <= n; i++) 
    sum = (1ll * sum + 1ll * C(n, i) * fac[i - 1] % mod * q_pow(n - 1, n - i) % mod) % mod;
  sum = 1ll * sum * q_pow(q_pow(n - 1, n), mod - 2) % mod;
  cout << sum;
}