洛谷 5437 「X Round 2」约定

写水题玩（

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

那么实际上只要算这张图上所有边权之和，乘上 2n 就是答案。
然后也不知道怎么的就考虑设边权和为 fn，寻找其递推式。
有 fn−fn−1=n−1∑i=1n∑j=i+1(i+j)k−n−2∑i=1n−1∑j=i+1(i+j)k=(2n−1)k+n−2∑i=1n∑j=i+1(i+j)k−n−2∑i=1n−1∑j=i+1(i+j)k=(2n−1)k+n−2∑i=1(n+i)k=2n−1∑i=n+1ik

于是我们搞出了一个一阶递推式。
然后就可以 O(n2) 做了好棒棒诶！

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

代码：

#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);
}