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

· · 题解

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

题目传送门

思路

对于每个点 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;
}