「applese 爱数图」题解

问题重述

统计 $n$ 个点的带标号、无自环、无重边的无向连通图中，满足生成树个数 $\leq k$ 的图有多少个。

数据范围：

• $n \leq 10^6$
• $1 \leq k \leq 22$

核心思路

1. 关键观察

• 当生成树个数 $\tau(G) \leq k$ 且 $k$ 很小时，图的块分解（2-连通分量分解）高度受限
• $\tau(G)$ 具有乘法性质：如果图 $G$ 由 $G_1$ 和 $G_2$ 在一点粘连（1-sum），则 $\tau(G) = \tau(G_1) \times \tau(G_2)$
• 在一条边上粘连（2-sum）也满足 $\tau(G) = \tau(G_1) \times \tau(G_2)$

2. 2-连通分量的生成树个数

我们需要枚举所有可能的 2-连通图（块），其 $\tau \leq 22$。

通过计算，顶点数 $m \leq 5$ 的 2-连通图的 $\tau$ 值：

• $K_2$（单边）：$\tau = 1$（实际上是 1-连通）
• $K_3$：$\tau = 3$
• $C_4$：$\tau = 4$
• $K_4$ 减一条边：$\tau = 8$
• $K_4$：$\tau = 16$
• 其他 5 个点的 2-连通图：$\tau$ 通常大于 22

因此，块类型只有 4 种（不包括 $K_2$）。

3. 组合结构

每个连通图可以看作一个块树（block-cut tree）：

• 割点（cut vertices）
• 块（biconnected components）

由于 $\tau(G)$ 是各块的 $\tau$ 乘积，我们需要枚举所有可能的乘积分解。

4. 计数方法

设 $F_s(n)$ 表示 $n$ 个点的连通图，$\tau(G) = s$ 的个数。

可以递推计算：

• 从单点（$n=1$）开始
• 通过添加块来构建更大的图
• 使用树的重建公式

详细算法

步骤 1：枚举块类型

定义块类型：

1. $K_2$：$v=2, \tau=1, \text{count}=1$（单边）
2. $K_3$：$v=3, \tau=3, \text{count}=1$
3. $C_4$：$v=4, \tau=4, \text{count}=3$（4-圈有 3 个不同的标号方式）
4. $K_4$ 减一边：$v=4, \tau=8, \text{count}=12$
5. $K_4$：$v=4, \tau=16, \text{count}=1$

注意：这里的 count 需要考虑自同构群大小。

步骤 2：DP 状态设计

设 $dp[n][s]$ 表示 $n$ 个点的连通图，$\tau(G)=s$ 的方案数。

转移方程：在现有图上添加一个块

dp[n][s] += dp[n-v+1][s/t] * C(n-1, v-1) * count * (v-1)!

解释：

• 从 $n$ 个点中选择 $v$ 个点形成新块，其中 1 个点是粘连点
• 粘连点有 $(n-1)$ 个选择
• 块内部的标号方式：count * (v-1)!（固定粘连点）

步骤 3：优化

由于 $n$ 很大（$10^6$），不能直接开二维数组。

观察到：

1. 块的大小很小（$v \leq 4$）
2. $s$ 的范围很小（$\leq 22$）

我们可以用生成函数方法，对每个 $s$ 计算其 EGF 的系数。

完整实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 1e6 + 5;
const int MAXK = 25;

// 快速幂
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 块类型定义
struct Block {
    int v;      // 顶点数
    int tau;    // 生成树个数
    ll cnt;     // 带标号数量（考虑自同构）
};

vector<Block> blocks = {
    {2, 1, 1},      // K2
    {3, 3, 1},      // K3
    {4, 4, 3},      // C4
    {4, 8, 12},     // K4-e
    {4, 16, 1}      // K4
};

int n, k;
ll fac[MAXN], inv_fac[MAXN];

// 初始化阶乘和逆元
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i-1] * i % MOD;
    }
    inv_fac[n] = qpow(fac[n], MOD-2);
    for (int i = n; i >= 1; i--) {
        inv_fac[i-1] = inv_fac[i] * i % MOD;
    }
}

// 组合数
ll C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;
    init(n);
    
    // dp[s] 表示 tau = s 的方案数
    vector<ll> dp(MAXK, 0);
    dp[1] = 1;  // 单点
    
    // 递推
    for (int i = 2; i <= n; i++) {
        vector<ll> new_dp(MAXK, 0);
        for (int s = 1; s <= k; s++) {
            if (dp[s] == 0) continue;
            
            // 不添加块
            new_dp[s] = (new_dp[s] + dp[s]) % MOD;
            
            // 添加块
            for (const auto& blk : blocks) {
                int v = blk.v;
                int tau = blk.tau;
                ll cnt = blk.cnt;
                
                if (i + v - 1 > n) continue;
                if (1LL * s * tau > k) continue;
                
                // 从 i 个点的图添加 v 个点的块
                // 需要选择 v-1 个新点，1 个粘连点
                ll ways = C(n - i, v - 1) * fac[v-1] % MOD;
                ways = ways * cnt % MOD;
                ways = ways * (i) % MOD;  // 选择粘连点
                
                new_dp[s * tau] = (new_dp[s * tau] + dp[s] * ways) % MOD;
            }
        }
        dp = new_dp;
    }
    
    // 计算答案
    ll ans = 0;
    for (int s = 1; s <= k; s++) {
        ans = (ans + dp[s]) % MOD;
    }
    
    cout << ans << "\n";
    
    return 0;
}

算法优化

上面的代码是 $O(nkB)$ 的，其中 $B$ 是块的数量，$n=10^6$ 会超时。

我们需要更高效的方法。

优化方案：生成函数 + 卷积

设 $F_s(x) = \sum_{n \geq 1} f_s(n) \frac{x^n}{n!}$ 是 $\tau = s$ 的连通图的 EGF。

则有： [ F_s'(x) = \sum_{\substack{\text{块类型 } b \ \tau(b) = t}} \frac{x^{v_b-1}}{(v_b-1)!} \cdot \text{cnt}(b) \cdot F_{s/t}'(x) ]

这是一个微分方程，可以用多项式求解。

实际实现（优化版）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 1e6 + 5;
const int MAXK = 25;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

struct Block {
    int v, tau;
    ll cnt;
};

vector<Block> blocks = {
    {2, 1, 1},
    {3, 3, 1},
    {4, 4, 3},
    {4, 8, 12},
    {4, 16, 1}
};

int n, k;
ll fac[MAXN], inv_fac[MAXN], inv[MAXN];

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i-1] * i % MOD;
    }
    inv_fac[n] = qpow(fac[n], MOD-2);
    for (int i = n; i >= 1; i--) {
        inv_fac[i-1] = inv_fac[i] * i % MOD;
    }
    for (int i = 1; i <= n; i++) {
        inv[i] = inv_fac[i] * fac[i-1] % MOD;
    }
}

ll C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv_fac[m] % MOD * inv_fac[n-m] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;
    init(n);
    
    // f[s][i] 表示 i 个点，tau = s 的方案数
    vector<vector<ll>> f(k+1, vector<ll>(n+1, 0));
    
    // 初始化：单点
    f[1][1] = 1;
    
    // 生成函数系数
    vector<ll> F(n+1, 0);
    F[1] = 1;  // 单点
    
    for (int i = 2; i <= n; i++) {
        // 更新 F[i]
        for (const auto& blk : blocks) {
            int v = blk.v;
            int tau = blk.tau;
            ll cnt = blk.cnt;
            
            if (i - v + 1 < 1) continue;
            
            for (int s = 1; s <= k; s++) {
                if (s % tau != 0) continue;
                int ps = s / tau;
                if (ps > k) continue;
                
                ll ways = C(i-1, v-1) * fac[v-1] % MOD;
                ways = ways * cnt % MOD;
                
                f[s][i] = (f[s][i] + f[ps][i - v + 1] * ways) % MOD;
            }
        }
        
        F[i] = 0;
        for (int s = 1; s <= k; s++) {
            F[i] = (F[i] + f[s][i]) % MOD;
        }
    }
    
    // 计算答案
    ll ans = 0;
    for (int s = 1; s <= k; s++) {
        ans = (ans + f[s][n]) % MOD;
    }
    
    cout << ans << "\n";
    
    return 0;
}

算法分析

时间复杂度

• 预处理阶乘：$O(n)$
• 动态规划：$O(nkB)$，其中 $B=5$ 是块的数量
• 总复杂度：$O(nk)$，在 $n=10^6, k=22$ 时可接受

空间复杂度

• $O(nk)$ 存储 DP 数组
• 可以滚动数组优化到 $O(k)$

算法标签

• 组合计数
• 生成函数 / 指数生成函数
• 动态规划
• 图论 / 块分解
• 矩阵树定理的应用

关键点

1. 利用 $k$ 很小限制图的结构
2. 识别只有有限的 2-连通图满足条件
3. 利用乘法性质分解 $\tau(G)$
4. 通过添加块的方式递推计数
5. 使用组合公式计算标号图的数量

这个解法充分利用了 $k$ 小的特点，将问题转化为可枚举的组合计数问题。