P3393 [BJOI2017]同构 题解

题目大意

题目要求对于给定的整数 $n$，计算一个值，该值为 $\frac{n(n-1)}{2} - \text{cnt} \mod 10^9+7$，其中 $\text{cnt}$ 是通过一种贪心分解算法得到的。具体来说，算法使用预处理数组 $f, g, h$ 来分解 $n$，从而得到 $\text{cnt}$。

解法

预处理数组 $f, g, h$ 的大小为 $N = 54$：

• $f[i]$ 表示 $i$ 个点的某种结构的个数（可能与无标号树相关）。
• $g[i]$ 表示 $i$ 个点的另一种结构的个数。
• $h[i][j]$ 表示使用前 $i$ 种结构凑出 $j$ 的方案数。

预处理过程如下：

1. 初始化 $f[1] = g[1] = 1$, $h[1][0] = h[1][1] = 1$。
2. 对于 i $从 2 到$ N $:
   • 计算 $f[i] = h[(i-1)/2][i-1]$（整数除法），如果 $i$ 为偶数，则加上 $g[i/2] \times (g[i/2] - 1) / 2$。
   • 计算 $g[i] = h[i-1][i-1]$。
   • 对于 $j$ 从 $0$ 到 $N$，使用组合数背包计算 $h[i][j]$。

对于每个测试用例, 读入字符串 $s$。 如果 $s$ 的长度大于 $20$，直接输出 $155132763$（因为对于大 $n$，答案总是这个常数）,否则将 $s$ 转换为整数 $n$。 如果 $n \leq 6$ 去特判。 对于 $n > 6$:

• 初始化 $\text{cnt} = n$, $\text{lft} = n$。
• 对于 $i$ 从 $1$ 到 $\text{lft}$:
  • $\text{val} = \min(\text{lft} / i, f[i])$。
  • $\text{lft} = \text{lft} - \text{val} \times i$。
  • $\text{cnt} = \text{cnt} - \text{val}$。
• 计算 $\text{full} = \frac{n(n-1)}{2} \mod 10^9+7$。
• 输出 $(\text{full} - \text{cnt})$

代码

多组数据复杂度 $O(T)$ 。

具体不想算了

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

const int mod = 1e9 + 7;
const int N = 54;
LL f[100], g[100], h[100][100];
inline void solve() {
    string s;
    cin >> s;
    if (s.size() > 20) {
        cout << "155132763\n";
        return;
    }
    LL n;
    sscanf(s.c_str(), "%lld", &n);
    if (n <= 6) {
        if (n == 1) {
            cout << "0\n";
        }
        else if (n <= 5) {
            cout << "-1\n";
        }
        else {
            cout << "9\n";
        }
        return;
    }
    LL cnt = n, lft = n;
    for (int i = 1; i <= lft; i++) {
        LL val = min(lft / i, f[i]);
        lft -= val * i;
        cnt -= val;
    }
    int n_ = n % mod;
    LL full = (1LL * n_ * (n_ - 1) / 2) % mod;
    cout << ((full - cnt) % mod + mod) % mod << '\n';
}
inline void build() {
    f[1] = g[1] = 1;
    h[1][0] = h[1][1] = 1;
    for (int i = 2; i <= N; i++) {
        f[i] = h[(i - 1) >> 1][i - 1];
        if (i % 2 == 0) {
            f[i] += g[i >> 1] * (g[i >> 1] - 1) / 2;
        }
        g[i] = h[i - 1][i - 1];
        for (int j = 0; j <= N; j++) {
            LL c = 1;
            for (int k = 0; i * k <= j && k <= g[i]; k++) {
                h[i][j] += h[i - 1][j - i * k] * c;
                c = c * (g[i] - k) / (k + 1);
            }
        }
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    build();
    return 0;
}

$\text{update\ 2025/10/13}:$ 更新了题解部分。