题解：P3993 [BJOI2017] 同构

· · 题解

某模拟赛赛时切题获得 rk2，写题解以纪念。

考虑原图的补图，就可以把边数最多转换成边数最少。

通过暴力可以验证 n=6 时不存在树，但有

1 2
1 3
2 3
2 4
3 5
5 6

这张图没有自同构但是不是一棵树，需要特判。

不妨设 n\ge7，可以证明补图是森林。

考虑反证法，设一个大小为 i 的连通分量不是树，设 f_i 表示大小为 i 的没有自同构的无根树的数量。

  1. 如果大小为 i 的连通分量中树的数量 <f_i，可以将这个连通分量替换成一个无自同构的树，显然边数会减少。
  2. 如果大小为 i 的连通分量中树的数量 =f_i，可以将这 i 个点连接到一个无自同构的树的直径上构成一条链，只要这个无自同构的树不是一个单点，那么就不会出现问题。
  3. 上面这个证明依赖于：补图中存在除了单点以外的无自同构的树，显然补图中单点的数量不能多于 1 个，否则就存在自同构：只交换这两个单点。
  4. 考虑极端情况，这个图里有一个单点，并且所有连通分量都不是树，此时总可以把整个图替换成一棵 n 个节点的树（因为 f_n>0）。

现在我们需要求 f_i。

根据 AHU 算法的思路，考虑钦定树的重心为根，分类讨论。

  1. 只有一个重心，那么这个重心的每棵子树相当于一棵 有根的 没有自同构的树，且不互同构，我们设 g_i 为大小为 i 的没有自同构的有根树的数量，只需要做一个背包即可，注意子树大小必须 \le\left\lfloor\dfrac{i-1}2\right\rfloor，以保证树的根是唯一重心。

子树是有根树的原因：如果这棵树有自同构，那么重心一定映射到重心，与重心相连的点映射后也与重心相连，这就相当于钦定与重心相连的点为根。

  1. 有两个重心，那么 i 必须是偶数，两个重心所在的子树必须没有自同构且不同构，且大小相等，均为 j=\dfrac i2，这种情况数为 \dfrac12g_j(g_j-1)。

考虑如何计算 g_i，与计算 f_i 的第一种情况类似，只是把子树大小的限制放宽到 <i，因为不需要保证根是唯一重心。

打个表观察，发现 f_{55} 就爆 long long 了，所以算 54 项就可以得到 90 分了。

如何得到 100 分？只需要求出 n=10^{100} 的答案即可，用 Python 算一算，结果是 155132763。

这个东西的时间复杂度能算，实际上，f_i 就是 OEIS A000220，其增长率为 \Theta(d^nn^{-5/2})，其中 d\approx2.518。

所以这个算法的时间复杂度为 O(\text{poly}\log n)，可以通过此题。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const int N = 54;
ll bao[N + 5], g[N + 5], f[N + 5];
ll min(ll a, ll b) {
    return a < b ? a : b;
}
char s[114];
int main() {
    g[1] = f[1] = 1;
    for (int i = 2; i <= N; i++) {
        bao[0] = 1;
        for (int j = 1; j < i; j++) {
            bao[j] = 0;
        }
        for (int j = 1; j <= (i - 1) / 2; j++) {
            // 拼接大小为 j 的无标号有根树.
            for (int k = i - 1; k >= 1; k--) {
                ll ans = 1;
                for (int l = 1; l * j <= k; l++) {
                    // 对大小 k 拼接 l 个.
                    if (l > g[j]) {
                        break;
                    }
                    ans = ans * (g[j] - l + 1) / l;
                    bao[k] += bao[k - l * j] * ans;
                }
            }
        }
        f[i] = bao[i - 1];
        if (i % 2 == 0) {
            f[i] += g[i / 2] * (g[i / 2] - 1) / 2;
        }
        bao[0] = 1;
        for (int j = 1; j < i; j++) {
            bao[j] = 0;
        }
        for (int j = 1; j < i; j++) {
            // 拼接大小为 j 的无标号有根树.
            for (int k = i - 1; k >= 1; k--) {
                ll ans = 1;
                for (int l = 1; l * j <= k; l++) {
                    // 拼接 l 个.
                    if (l > g[j]) {
                        break;
                    }
                    ans = ans * (g[j] - l + 1) / l;
                    bao[k] += bao[k - l * j] * ans;
                }
            }
        }
        g[i] = bao[i - 1];
    }
    int T;
    scanf("%d", &T);
    for (ll n; T != 0; T--) {
        scanf("%s", s);
        if (strlen(s) <= 19) {
            n = 0;
            for (int i = 0; s[i] != '\0'; i++) {
                n = n * 10 + s[i] - '0';
            }
        } else {
            printf("155132763\n");
            continue;
        }
        if (n == 1) {
            printf("0\n");
        } else if (n <= 5) {
            printf("-1\n");
        } else if (n == 6) {
            printf("9\n");
        } else {
            ll ans;
            if (n % 2 == 0) {
                ans = (n / 2 % mod) * ((n - 3) % mod) % mod;
            } else {
                ans = (n % mod) * ((n - 3) / 2 % mod) % mod;
            }
            ll cnt = 0;
            for (int i = 1; i <= N; i++) {
                if (n < i) {
                    break;
                }
                cnt += min(f[i], n / i);
                n -= i * min(f[i], n / i);
            }
            printf("%lld\n", (ans + cnt % mod) % mod);
        }
    }
    return 0;
}