自动搬运

查看原文

来自洛谷，原作者为

	Tx_Lcy ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็树不要皮，必死无疑；人不要脸，天下无敌

搬运于2025-08-24 22:30:13，当前版本为作者最后更新于2022-08-29 20:49:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最近在补期望，于是就找到了这道好题，感觉题解的叙述有些过于高大上，我以我自己的理解简单地叙述一下。

题目传送门

思路

对于每个点 $i$，连 $1$ 条边的概率为 $100\%$，再连一条边的概率为 $\frac{1}{n}$，以此类推。我们不妨设 $edge_i$ 为 $i$ 的期望边数。

显然，$edge_i=1 \times(1+\frac{1}{n}+\frac{1}{n^2}+...)$，则 $n \times edge_i=1 \times (n+1+\frac{1}{n}+\frac{1}{n^2}+...)$，两式相减，得 $(n-1) \times edge_i=n$，$edge_i=\frac{n}{n-1}$，$\sum edge_i=n \times \frac{n}{n-1}=\frac{n^2}{n-1}$。

所以，第一问的答案就是 $\frac{n^2}{n-1}$。

关于第二问，我们可以发现，自己与自己连边显然对答案无影响，所以我们不考虑自环，这样边的总数即是 $n$ 条，由于有可能有重边，所以不一定是联通的，但在每个连通块内部一定是边与点数相同，即为一颗基环树。所以设连通块数为 $ans$，我们发现 $ans=$ $sum$ 基环树 $=$ $sum$ 环。

所以第二问等价于求环的个数。

我们先求出这张图有多少种可能性，我们记为 $maxn$，显然，每个节点有 $n-1$ 种不同的连法，不需要考虑重边，所以我们直接乘法原理，得到 $maxn=(n-1)^n$。

接下来我们考虑在所有图中出现的环的总数，我们记为 $maxx$，我们按照环的大小分类讨论，设环的大小为 $i$，则 $2 \le i \le n$。对于一个确定的 $i$，可能出现的环的总数为 $C_n^i \times (i-1)! \times (n-1)^{n-i}$，通俗地讲，$C_n^i$ 表示从 $n$ 个节点里面随便选 $i$ 个点，让它们组成环，它们内部的边的种类有 $(i-1)!$ 种，而别的点的可能性有 $(n-1)^{n-i}$ 种，我们根据乘法原理都乘起来即可。，所以 $maxx=\sum_{i=2}^n C_n^i \times (i-1)! \times (n-1)^{n-i}$。

所以，第二问的答案就是 $\frac{maxx}{maxn}=\frac{\sum_{i=2}^n C_n^i \times (i-1)! \times (n-1)^{n-i}}{(n-1)^n}$。

当然，这个答案柿子仍然可以化简，这就交由各位读者自己去完成了，此处不再赘述。

代码

弄明白了过程，代码很好写。

//A tree without skin will surely die. 
//A man without face is invincible.
#include<bits/stdc++.h>
#define int long long
#define rint register int
using namespace std;
int const mod=998244353;
int const N=1e4+10;
int fac[N],facn[N];
#define inv(x) (qpow(x,mod-2))
inline int qpow(int a,int b){
    int ans=1;
    while (b){
        if (b&1) ans*=a,ans%=mod;
        a*=a,a%=mod,b>>=1;
    }
    return ans;
}
inline int C(int n,int m){return fac[n]*inv(fac[m])%mod*inv(fac[n-m])%mod;}
signed main(){
    ios::sync_with_stdio(false);
    cout.tie(0),cout.tie(0);
    int n;cin>>n;
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=fac[i-1]*i,fac[i]%=mod;
    facn[0]=1;
    for (int i=1;i<=n;++i) facn[i]=facn[i-1]*(n-1),facn[i]%=mod;//预处理 (n-1) 的次方
    cout<<n*n%mod*inv(n-1)%mod<<'\n';
    int ans=0;
    for (int i=2;i<=n;++i) ans+=(C(n,i)*fac[i-1]%mod*facn[n-i]%mod),ans%=mod;
    cout<<ans*inv(facn[n])%mod<<'\n';
    return 0;
}