CF1580B Mathematics Curriculum 题解

题意：

求长度为 $n$ 且恰好有 $K$ 个 $m$ – 好数的排列个数：

称一个数是 $m$ – 好数当且仅当所有包含这个数的区间中，不同的最大值的个数恰有 $m$ 个。

答案对 $P$ 取模。

输入格式

第一行给出四个整数 $n, m, K, P~(1 \le n \le 100, 1 \le m \le n, 1 \le K \le n, 1 \le P \le 10^9)$

输出格式

输出方案数模 $P$ 的结果。

设 $f(i,j,k)$ 表示长度为 $i$ 且恰好有 $j$ 个 $k$ – 好数的方案数。考虑转移。

枚举最大值的位置 $p$ ，那么划分方案数等于剩下的 $i-1$ 个数里选 $p-1$ 个放到左侧（内部顺序不考虑）

由于跨越 $p$ 的区间都会吃到 $p$ 给的贡献 $1$ ，所以我们要从 $(k-1)$ – 好数转移，那么

$f(i, j, k)=\sum_{p}\binom{i-1}{p-1}\sum_c f(p-1,\, c,\, k-1) \cdot f(i-p,\, j-c-[k=1],\, k-1)$

时间复杂度 $\mathcal{O}(n^5)$ ，实际上根本跑不满。

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(114))

int n, m, K, mod, f[N][N][N], fac[N], C[N][N];
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
int get(int i, int j, int k)
{
    if(!j && (k > i || k < 1)) return fac[i];
    return f[i][j][k];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> K >> mod; f[1][1][1] = C[0][0] = fac[0] = 1;
    rep(i, 1, n)
    {
        C[i][0] = 1; fac[i] = fac[i - 1] * i % mod;
        rep(j, 1, n) { add(C[i][j] = C[i - 1][j], C[i - 1][j - 1]); }
    }
    rep(i, 2, n) rep(j, 0, min(i, K)) rep(k, 1, min(i - j + 1, m))
    {
        const int G = j - (k == 1); int x, y;
        f[i][j][k] = get(i - 1, G, k - 1) * 2 % mod;
        rep(p, 2, i - 1) rep(c, 0, min(p, G)) {
            if((x = get(p - 1, c, k - 1)) && (y = get(i - p, G - c, k - 1)))
                add(f[i][j][k], x * y % mod * C[i - 1][p - 1] % mod);
        }
    }
    cout << f[n][K][m] << '\n';
    return 0;
}