洛谷 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);
}