题意
对于每个点 $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
$$
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})
$$
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}
$$
\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}
$$
S=\frac{1}{(1-q)^2}
$$
期望为：
$$
E=p\cdot S=\frac{p}{(1-q)^2}=\frac{1}{p}
$$
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}
$$
\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}
$$
E=\frac{\text{所有图中环的总数}}{\text{图的总数}}=\frac{A}{B}
$$
每个点都可以向外连边，图的总数为：
$$
B=(n-1)^n
$$
B=(n-1)^n
$$
环的总数：先枚举环的点数 $i$，再确定哪些点在环上，其余点可以随便连边，环上的点再圆排列。
$$
A=\sum_{i=2}^n \binom{n}{i}\cdot (n-1)^{n-i}\cdot (i-1)!
$$
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}
$$
\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;
}