题解：P11174 「CMOI R1」Looking For Edge Of Ground／City Planning

· · 题解

可以发现，一张图 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 月，@NaCly_Fish 对于 [WC2019] 数树 的 \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;
}

我个人对出题人 @Argon_Cube 在明知 @NaCly_Fish 的文章的情况下，未确认本题的题意经过简单的处理后与 [WC2019] 数树 完全一致的非专业精神表示批评，对 @NaCly_Fish 明知题意完全一致却以普及的目的未阻止本题的出现表示 。