自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:10:44，当前版本为作者最后更新于2019-05-29 22:10:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

【XR-2】约定 题解

先说句闲话（雾）

验题人 EntropyIncreaser 对这题是这么说的：“虽然比较裸，但是还是需要比较有经验啊”。

出题人只会出裸题，菜爆了 qaq

题目大意

$n$ 个点的无向完全图，编号从 $1$ 到 $n$。$u,v$ 之间的边权为 $(u+v)^k$，求这个图的生成树期望边权和。

前置知识

• 期望
• 生成树
• 拉格朗日插值
• 线性求逆元

题解

一个无向完全图有 $n^{n-2}$ 棵生成树，总共就有 $(n-1)n^{n-2}$ 条边。而完全图中一共有 $\frac{n(n-1)}{2}$ 条边，可以发现，每条边在生成树中均出现 $2n^{n-3}$ 次。

于是我们可以推出一个式子：

$$\large ans=\frac{2n^{n-3}}{n^{n-2}}\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k=\frac{2}{n}\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k $$

这样就可以暴力计算，预处理一下自然数$k$次幂，就可以做到 $\Theta(n^2)$ 了。

但是这样显然是不够优秀的，我们考虑优化。

设：

$$\large a_n=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k $$

那么做一下差分

$$\large a_{n}-a_{n-1}=\sum\limits_{i=n+1}^{2n-1}i^k $$

然后这样就能 $\Theta(n\log k)$ 来搞，但还是太慢。

注意到 $a_n$ 关于 $n$ 是一个多项式，稍微冷静分析一下，就发现这是 $k+2$ 次的。

看到这里，很显然需要用拉格朗日插值了。不过我们可以连续取值，直接算出前 $k$ 项的复杂度为 $\Theta(k\log k)$，插值的地方是 $\Theta(k)$ 的。

然而还是不能通过，考虑继续优化。

对于这样一个函数：

$$\large f(x)=x^k$$

显然它是个完全积性函数，可以用线性筛 $\Theta(k)$ 算出 $[1,k]$ 中所有 $f(x)$ 的值。

复杂度的证明很简单，小于 $k$ 的质数约为 $\lfloor k/\ln k \rfloor$ 个，做一次快速幂的是 $\Theta(\log k)$。而快速幂只会在筛到质数的时候做，所以复杂度为 $\Theta((k/\log k)\times\log k)=\Theta(k)$。

最后就是我们在做拉格朗日插值时，会用到求逆元。如果用快速幂或 exgcd 来求的话，还是会比较慢。

所以用一下【模板】乘法逆元2 的套路，线性求一波即可。

当然你也可以用前后缀积直接解决。

把算出来的 $a_n$ 乘 $2$ 再除以 $n$ 即是答案。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 20000007
#define p 998244353
#define ll long long
#define reg register
using namespace std;

inline void read(int &x);
void print(int x);
inline int power(int a,int t);
int solve();

inline int add(int a,int b){
    return a+b>=p?a+b-p:a+b;
}

inline int dec(int a,int b){
    return a<b?a-b+p:a-b;
}

int n,k,lim,ans,cnt;
int f[N],s[N],inv[N],fac[N];

int main(){
    read(n),read(k);
    lim = min((k+3),n+1)<<1;
    s[1] = 1;
    for(reg int i=2;i<=lim;++i){
        if(!s[i]){
            f[++cnt] = i;
            s[i] = power(i,k);
        }
        for(reg int j=1;j<=cnt&&i*f[j]<=lim;++j){
            s[i*f[j]] = (ll)s[i]*s[f[j]]%p;
            if(i%f[j]==0) break;
        }
    }
    for(reg int i=2;i<=lim;++i) s[i] = add(s[i],s[i-1]);
    lim >>= 1;
    f[1] = 0;
    f[2] = power(3,k);
    for(reg int i=3;i<=lim;++i)
        f[i] = add(f[i-1],dec(s[(i<<1)-1],s[i]));
    if(n<=lim) ans = f[n];
    else ans = solve();
    ans = (ll)(ans<<1)*power(n,p-2)%p;
    print(ans);
    return 0;
}

int solve(){
    s[0] = s[1] = 1;
    for(reg int i=2;i<=lim;++i)
        s[i] = (ll)s[i-1]*i%p;
    fac[0] = 1;
    reg int g,mul = 1,res = 0;
    for(reg int i=1;i<=lim;++i){
        mul = (ll)mul*(n-i)%p;
        inv[i] = fac[i] = (ll)s[i-1]*s[lim-i]%p*(n-i)%p;
    }
    for(reg int i=2;i<=lim;++i)
        fac[i] = (ll)fac[i-1]*fac[i]%p;
    fac[lim] = power(fac[lim],p-2);
    for(reg int i=lim;i>=1;--i){
        g = inv[i];
        inv[i] = (ll)fac[i-1]*fac[i]%p;
        fac[i-1] = (ll)g*fac[i]%p;
    }
    for(reg int i=1;i<=lim;++i){
        g = (ll)f[i]*mul%p*inv[i]%p;
        if((lim-i)&1) g = (ll)g*(p-1)%p;
        res = add(res,g);
    }	
    return res;
}

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

拓展

以上都是在 $n\neq 998244353$ 的前提下讨论的。

而对于 $n = 998244353$ 这种特殊情况，这里就多扯一句。

首先容易证明插值出来的这个多项式，常数项为 $0$。

要求的答案是 $\large \frac{2a_n}{n} \mod n$ ，相当于求 $2\times[n^1]a_n$。

那么只要求出其一次项系数乘 $2$，就是答案了。

由于只用求一次项，所以可以按照二项式的方法来算，更高次的直接忽略掉，对答案没有影响。

还有就是预处理一下二项式的前后缀积，做法和前面的很类似。

$$\large f(x)=\sum\limits_{i=1}^n\frac{f(i)(-1)^{n-i}}{(i-1)!(n-i)!}\prod_{j\neq i}(x-j) $$

这个式子就是前半部分把阶乘逆元预处理好，后半部分就是刚才说的前后缀积处理。

两种情况的时间复杂度都为 $\Theta(k)$。

对了，既然此题是用的小圆作为题面，那就在题解的最后放上一张图吧~