P7278 纯洁憧憬

Semsue · 2023-01-23 20:52:37 · 题解

当年 alpha 叫我来帮忙验题，然后发现我不会析合树。最近突然想起来再看这道题，发现也没有那么困难。

至少比较难做，所以换成不存在。

考虑根为合点的时候，这时任意一个非平凡的儿子段都是一个连续段，最长的一定是去掉第一个或最后一个儿子。那么说明这两个儿子都至少是 n-k。设 g_n 代表长度为 n 的且不存在一个包含 1 的前缀使得其实一个连续段，简单容斥即可得到。

然后枚举第一个儿子和最后一个儿子的大小，对答案的贡献即为

再考虑根为析点的个数，只用对每个儿子节点长度都不大于 k 的情况计数。

设 f_n 为长度为 n 的排列不存在非平凡连续段的方案数，即 Interval-free permutation 这道题在求的东西。然后再求出 h_{n,m} 代表 n 个数分成 m 个不同区间的方案数。

那么贡献就是

最后的复杂度即为 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int add(int a, int b) {
    return a + b >= mod ? a + b - mod : a + b;
}
int dec(int a, int b) {
    return a < b ? a - b + mod : a - b;
}
int mul(int a, int b) {
    return 1ll * a * b % mod;
}
int ksm(int a, int b = mod - 2) {
    int ret = 1;
    while (b) {
        if (b & 1) {
            ret = mul(ret, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return ret;
}
template <typename T>
void read(T &x) {
    T sgn = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) {
        if (ch == '-') {
            sgn = -1;
        }
    }
    for (x = 0; isdigit(ch); ch = getchar()) {
        x = x * 10 + ch - '0';
    }
    x *= sgn;
}
int n, m, fac[405], f[405], g[405], h[405][405], F[405][405], ans;
int main() {
    read(n);
    read(m);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = mul(fac[i - 1], i);
    }
    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        g[i] = fac[i];
        for (int j = 1; j < i; j++) {
            g[i] = dec(g[i], mul(fac[i - j], g[j]));
        }
    }
    F[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = 1; k <= i; k++) {
                F[i][j] = add(F[i][j], mul(F[i - k][j - 1], fac[k]));
            }
        }
    }
    f[1] = 1;
    f[2] = 2;
    for (int i = 3; i <= n; i++) {
        f[i] = fac[i];
        for (int j = 1; j < i; j++) {
            f[i] = dec(f[i], mul(2, mul(g[j], fac[i - j])));
        }
        for (int j = 4; j < i; j++) {
            f[i] = dec(f[i], mul(f[j], F[i][j]));
        }
    }
    h[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = 1; k <= min(i, m); k++) {
                h[i][j] = add(h[i][j], mul(h[i - k][j - 1], fac[k]));
            }
        }
    }
    ans = fac[n];
    for (int i = n - m; i <= n; i++) {
        for (int j = n - m; j <= n; j++) {
            if (i + j <= n) {
                ans = dec(ans, mul(2, mul(mul(g[i], g[j]), fac[n - i - j])));
            }
        }
    }
    for (int i = 4; i <= n; i++) {
        ans = dec(ans, mul(f[i], h[n][i]));
    }
    printf("%d\n", ans);
    return 0;
}