洛谷 5437.「X Round 2」约定

写水题玩(

首先一个 \(n\) 点无向完全图的生成树个数,等价于 \(n\) 点无根树的个数。
而根据 Prufer 序列,这样的树有 \(n^{n-2}\) 棵。
显然边是均匀分布的,故每条边的出现次数就是生成树总边数除以无向完全图的边数,即 \(\frac{(n-1)n^{n-2}}{\binom n2}=2n^{n-3}\)
所以每条边出现的概率为 \(\frac{2n^{n-3}}{n^{n-2}}=\frac2n\)

那么实际上只要算这张图上所有边权之和,乘上 \(\frac2n\) 就是答案。
然后也不知道怎么的就考虑设边权和为 \(f_n\),寻找其递推式。
\[ \begin{aligned} f_n-f_{n-1} &= \sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k-\sum\limits_{i=1}^{n-2}\sum\limits_{j=i+1}^{n-1}(i+j)^k \\ &= (2n-1)^k + \sum\limits_{i=1}^{n-2}\sum\limits_{j=i+1}^n(i+j)^k - \sum\limits_{i=1}^{n-2}\sum\limits_{j=i+1}^{n-1}(i+j)^k \\ &= (2n-1)^k + \sum\limits_{i=1}^{n-2} (n+i)^k \\ &= \sum\limits_{i=n+1}^{2n-1} i^k \end{aligned} \]

于是我们搞出了一个一阶递推式。
然后就可以 \(O(n^2)\) 做了好棒棒诶!

注意到这是个 \(k+1\) 次多项式,那么 \(f_n\) 显然也是个关于 \(n\)\(k+2\) 次多项式。
所以线性筛求出所有 \(i^k\) 并预处理前后缀积、阶乘及阶乘的逆,拉格朗日插值即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
using namespace std;
const int MX = 2e7 + 6;
const int K = 1e7;
const int mod = 998244353;
int n,k,lim;
int fac[MX + 5],ifac[MX + 5],prod[2][MX + 5],f[MX + 5];
int vis[MX + 5],cnt,prime[MX + 5],sum[MX + 5];
int ans;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int main()
{
scanf("%d%d",&n,&k),lim = k + 3 << 1,sum[1] = fac[0] = prod[0][0] = 1;
for(register int i = 2;i <= lim;++i)
{
if(!vis[i])
prime[++cnt] = i,sum[i] = fpow(i,k);
for(register int j = 1;j <= cnt && i * prime[j] <= lim;++j)
{
vis[i * prime[j]] = 1,sum[i * prime[j]] = (long long)sum[i] * sum[prime[j]] % mod;
if(!(i % prime[j]))
break;
}
}
for(register int i = 1;i <= lim;++i)
sum[i] = (sum[i] + sum[i - 1]) % mod;
prod[1][(lim >>= 1) + 1] = 1;
for(register int i = 2;i <= lim;++i)
f[i] = (f[i - 1] + (sum[2 * i - 1] - sum[i] + mod) % mod) % mod;
for(register int i = 1;i <= lim;++i)
fac[i] = (long long)fac[i - 1] * i % mod,
prod[0][i] = (long long)prod[0][i - 1] * (n - i + mod) % mod;
ifac[lim] = fpow(fac[lim],mod - 2);
for(register int i = lim;i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod,
prod[1][i] = (long long)prod[1][i + 1] * (n - i + mod) % mod;
for(register int i = 1,temp;i <= lim;++i)
temp = (long long)f[i] * prod[0][i - 1] % mod * prod[1][i + 1] % mod * ifac[i - 1] % mod * ifac[lim - i] % mod,
lim - i & 1 ? (ans = (ans - temp + mod) % mod) : (ans = (ans + temp) % mod);
ans = 2LL * ans % mod * fpow(n,mod - 2) % mod;
printf("%d\n",ans);
}