自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 23:04:56，当前版本为作者最后更新于2024-10-07 20:28:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

可以发现，一张图 $G$ 的 $f(G)$ 值就是它的生成树个数，即有多少棵树 $T$ 满足 $T$ 是 $G$ 的子图。

在固定点集 $V = [n]$ 的记号下，我们用简单无向图的边集来指称这张图。上面的式子可以记为 $f(G) = \sum_T [T \subseteq G]$，这里 $\sum_T$ 表示对所有树求和。

对于答案，我们有

$$\begin{aligned} \mathrm{Ans} &= \sum_G f(G)^2 \\ &= \sum_G \Biggl( \sum_T [T \subseteq G] \Biggr)^2 \\ &= \sum_G \sum_{T_1} \sum_{T_2} [T_1 \subseteq G] [T_2 \subseteq G] \\ &= \sum_{T_1} \sum_{T_2} \sum_G [T_1 \subseteq G] [T_2 \subseteq G] \\ &= \sum_{T_1} \sum_{T_2} \sum_G [G \supseteq T_1 \cup T_2] \end{aligned} $$

我们考虑一下当 $T_1, T_2$ 固定时，满足上式的 $G$ 的结构。所有可能的边有 $\binom{n}{2}$ 条，而其中 $\lvert T_1 \cup T_2 \rvert$ 条是强制选的，剩下的都可以自由决策是否加入 $G$ 中。也就是说，如上 $G$ 的数量为 $2^{\binom n 2 - \lvert T_1 \cup T_2 \rvert}$。我们继续化简答案

$$\begin{aligned} \mathrm{Ans} &= \sum_{T_1} \sum_{T_2} \sum_G [G \supseteq T_1 \cup T_2] \\ &= \sum_{T_1} \sum_{T_2} 2^{\binom{n}{2} - \lvert T_1 \cup T_2 \rvert} \\ &= \sum_{T_1} \sum_{T_2} 2^{\binom{n}{2} - (\lvert T_1 \rvert + \lvert T_2 \rvert - \lvert T_1 \cap T_2 \rvert)} \\ &= \sum_{T_1} \sum_{T_2} 2^{\binom{n}{2} - (n - 1) - (n - 1) + \lvert T_1 \cap T_2 \rvert} \\ &= 2^{\binom{n}{2} - (n - 1) + 1} \sum_{T_1} \sum_{T_2} 2^{-(n - \lvert T_1 \cap T_2 \rvert)} \\ &= 2^{\binom{n - 1}{2} + 1} \sum_{T_1} \sum_{T_2} (1 / 2)^{n - \lvert T_1 \cap T_2 \rvert} \end{aligned} $$

其中，注意把 $T_1 \cup T_2$ 改为 $T_1 \cap T_2$ 时使用了容斥原理。这里的代数变形的目的再明显不过了：如果你对 [WC2019] 数树 有印象，指数上的 $n - \lvert T_1 \cap T_2 \rvert$ 应该对你而言很熟悉——这就是图 $T_1 \cap T_2$ 的连通块数，而这恰好就是 [WC2019] 数树 的 $\mathrm{op} = 2$ 的情况之所欲求，即 $y$ 的连通块数次方。这里 $y$ 取 $1 / 2$。

换句话说，设 [WC2019] 数树 中 $(n, y, \mathrm{op}) = (n, 1/2, 2)$ 的答案为 $\mathrm{Ans}'$，则本题答案为 $\mathrm{Ans} = 2^{\binom{n - 1}{2} + 1} \cdot \mathrm{Ans}'$。

主流的对 [WC2019] 数树 的解法调用了多项式 exp，直接在本题中进行实现可以获得 75 分。

若不是在 2024 年 6 月，

的 $\mathrm{op} = 2$ 的情况给出了针对 $\displaystyle [x^n] \exp \Biggl( k \sum_{i \ge 1} \frac{i^i}{i!} x^i \Biggr)$（[WC2019] 数树 中需要处理的核心问题）使用 $\displaystyle T(x) = \sum_{i \ge 1} \frac{i^{i - 1}}{i!} x^i$ 满足的方程 $T(x) = x \mathrm{e}^{T(x)}$ 进行化简，然后再施以另类 Lagrange 反演，从而获得形如 $\displaystyle [x^n] \exp \biggl( \frac{a x}{1 - x} + b x \biggr)$ 形式的结果（而这显然是整式递推的），我们可能永远都无法发现 [WC2019] 数树 背后的整式递推性。

既然 [WC2019] 数树 的整式递推性确立了，本题的 $\mathcal O(n)$ 甚至 $\tilde{\mathcal O}(\sqrt{n})$ 做法也就迎刃而解。在此我援引 @NaCly_Fish 的文章 [WC2019] 数树 op=2 线性做法题解 & 闲话 以供参考（例如代数推导的细节、以及具体的整式递推式）。

AC 代码如下（就是 @NaCly_Fish 在 [WC2019] 数树 中的提交 R161859081 删除了 $\mathrm{op} \ne 2$ 的部分，设置 $y = 1/2$，并在输出时对答案乘了个系数），时间复杂度为 $\mathcal O(n)$。

// credit to NaCly_Fish.
// https://www.luogu.com/article/mrz7ixcb
// Code from <https://www.luogu.com.cn/record/161859081>

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#define ll long long
#define p 998244353
#define N 67109000
using namespace std;

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

int inv[N],fac[N];

void init(int n){
    fac[0] = fac[1] = inv[1] = 1;
    for(int i=2;i<=n;++i){
        fac[i] = (ll)fac[i-1]*i%p;
        inv[i] = -(ll)(p/i)*inv[p%i]%p;
    }
}

int coef(int a,int b,int n){ // n! [x^n] exp(ax/(1-x) + bx)(1-x)
    static int f[N];
    f[0] = 1,f[1] = a+b,f[2] = (a + (ll)inv[2]*(a+b)%p*(a+b))%p;
    for(int i=2;i<n;++i) f[i+1] = ((a+b+2ll*i)*f[i] - (2ll*b+i-1)*f[i-1] + (ll)b*f[i-2])%p*inv[i+1]%p;
    return (ll)(f[n]-f[n-1])*fac[n]%p;
}

int solve2(int n,int y){
    int a = (ll)n*n%p*y%p*power(1-y,p-2)%p,b = n;
    int res = (ll)coef(a,b,n)*power(1-y,n)%p*power(n,p-5)%p;
    return (res+p)%p;
}

int n,y,op;

int main(){
    init(33555000);
    scanf("%d",&n);
    y=(p+1)/2;
    printf("%d",(int)((ll)solve2(n,y)*power(2,(int)(((ll)(n-1)*(n-2)/2+1)%(p-1)))%p));
    return 0;
}

我个人对出题人

Cly_Fish 的文章的情况下，未确认本题的题意经过简单的处理后与 [WC2019] 数树 完全一致](/discuss/949820#:~:text=%E6%88%91%E7%9C%8B%E8%BF%87%E4%BA%86%E7%A5%9E%E9%B1%BC%E5%9C%A8%E6%9C%AC%E9%A2%98%E7%9A%84%E9%A2%98%E8%A7%A3%EF%BC%8C%E4%BD%86%E6%98%AF%E7%9C%8B%E5%88%B0%E8%83%BD%E7%94%A8%E8%BF%99%E4%B8%AA%20Trick%20%E4%BC%98%E5%8C%96%E8%87%AA%E5%B7%B1%E7%9A%84%E9%A2%98%E5%B0%B1%E8%B7%91%E4%BA%86%EF%BC%8C%E6%B2%A1%E6%9C%89%E4%BB%94%E7%BB%86%E7%9C%8B%E8%BF%87%E5%8E%9F%E9%A2%98%E9%9D%A2)的非专业精神表示批评，对 @NaCly_Fish 明知题意完全一致却以普及的目的未阻止本题的出现表示 。