CF1874E 题解

· · 个人记录

实际上函数就是返回这个神秘分治的执行次数，所以对着这个 dp 就可以了。

设 dp_{i,j} 为排列长度为 i，函数值为 j 的排列个数。直接枚举序列第一项是啥得到：

dp_{i,j}=\sum^i_{k=1}\dbinom{i-1}{k-1}\sum^{j-i}_tdp_{k-1,t}dp_{i-k,j-i-t}

然后后半部分看着就很卷积，于是生成函数直接启动！设 F_i(x)=\sum_jdp_{i,j}x^i，得到：

F_i(x)=x^i\sum^i_{j=1}\dbinom{i-1}{j-1}F_{j-1}(x)F_{i-j}(x)

然后下一步就很玄学了。由于 F 只有 \binom{n+1}2 项，也就是我们只要代进 \binom{n+1}2+1 个数值进去就能暴力把结果插出来。总时间复杂度是 O(n^4)，不过跑不满。

注意算点值一定要所有一起算，不要一个一个单独 dp，因为 cf 神机会把连续寻址吞了然后导致你跑得比本地还慢（悲）。

AC 代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;

const int MAXN = 2e2 + 10;
const int MAXM = 4e4 + 10;
const int mod = 1e9 + 7;

int n, m, k;

ll c[MAXN][MAXN], inv[MAXM], ifac[MAXM], p[MAXM][MAXN], dp[MAXN][MAXM];

ll t[MAXM], f[MAXM], ans, x;

int main() {
    scanf("%d%d", &n, &k), m = n * (n + 1) >> 1;
    for (int i = 0; i <= n; i++) c[i][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    inv[1] = *ifac = 1;
    for (int i = 2; i <= m; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= m; i++) ifac[i] = ifac[i - 1] * inv[i] % mod;
    for (int i = 0; i <= m; i++) dp[0][i] = 1;
    for (int i = 1; i <= m; i++) {
        p[i][0] = 1;
        for (int j = 1; j <= n; j++) p[i][j] = p[i][j - 1] * i % mod;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int l = 0; l <= m; l++) dp[i][l] = (dp[i][l] + dp[j - 1][l] * dp[i - j][l] % mod * c[i - 1][j - 1]) % mod;
        }
        for (int l = 0; l <= m; l++) dp[i][l] = dp[i][l] * p[l][i] % mod;
    }
    *t = 1;
    for (int i = 0; i <= m; i++) {
        for (int j = m; j; j--) t[j] = (t[j] * (mod - i) + t[j - 1]) % mod;
        *t = *t * (mod - i) % mod;
    }
    for (int i = 1; i <= m; i++) {
        if (!dp[n][i]) continue; x = dp[n][i] * ifac[i] % mod * ifac[m - i] % mod;
        if (m - i & 1) x = mod - x;
        *f = *t * (mod - inv[i]) % mod;
        for (int j = 1; j <= m; j++) f[j] = (t[j] - f[j - 1] + mod) % mod * (mod - inv[i]) % mod;
        for (int j = k; j <= m; j++) ans = (ans + x * f[j]) % mod;
    }
    printf("%lld", ans);
}