专栏文章

CF 2066D2 Club of Young Aircraft Builders (hard version)

rrizynvu
CF2066D2题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioxn4fs
此快照首次捕获于
2025/12/03 02:49
3 个月前
此快照最后确认于
2025/12/03 02:49
3 个月前
查看原文
cnblogs。
说一个看起来暴力得多的做法！
考虑对于 ii 只有在 i∼ni\sim n 层飞出的纸飞机数量 <c< c 时才能飞一个纸飞机。
那么如果知道了当前每个楼层飞出的纸飞机数，考虑找到最小的 ii 满足 i∼ni\sim n 层飞出的纸飞机数 <c< c，此时就相当于是只有 i∼ni\sim n 层可以飞出纸飞机。
发现这就天然的分出了阶段：1∼n1\sim n 层都可以飞纸飞机，2∼n2\sim n 层可以飞纸飞机，一直到最后第 nn 层的纸飞机也飞完结束。
于是考虑记 fi,j,kf_{i, j, k} 表示考虑了前 ii 个纸飞机，此时 j∼nj\sim n 层还可以飞纸飞机，且 j∼nj\sim n 层一共飞了 kk 个纸飞机的方案数。
为了方便转移，考虑延后计算贡献，就是此时不去区分 j∼nj\sim n 层具体的分法，到阶段结束时再考虑计算贡献。
具体来说对于转移，考虑分为两种：
  • k+1<ck + 1 < c，那么直接飞一个纸飞机即可 fi,j,k→fi+1,j,k+1f_{i, j, k}\to f_{i + 1, j, k + 1}。
  • k+1=ck + 1 = c，那么之后 jj 这一层就不能飞纸飞机了，考虑枚举 jj 这一层在之前飞了多少个纸飞机。
    具体来说，记 1∼i1\sim i 中 ai′>ja_{i'} > j 的数量为 c1c_1，ai′=ja_{i'} = j 的数量为 c2c_2，那么还有 k−c1−c2k - c_1 - c_2 个纸飞机没有确定，枚举 x∈[c2.k−c1]x\in [c_2. k - c_1] 表示 jj 层的纸飞机数，转移为 (k−c1−c2x−c2)fi,j,k→fi+1,j+1,k−x\binom{k - c_1 - c_2}{x - c_2}f_{i, j, k}\to f_{i + 1, j + 1, k - x}。
    需要注意可能 jj 这一层飞出去了 00 个纸飞机，所以 j+1∼nj + 1\sim n 的纸飞机数仍为 kk，要继续删掉 j+1j + 1 层。
还需要考虑的是，如果遇到了 ai>0a_i > 0，说明此时 aia_i 一定能够飞纸飞机，所以 jj 的合法范围应为 [1,ai][1, a_i]。
k+1<ck + 1 < c 时状态数 O(nmc)\mathcal{O}(nmc) 转移 O(1)\mathcal{O}(1)，k+1=ck + 1 = c 时状态数 O(nm)\mathcal{O}(nm) 转移 O(c)\mathcal{O}(c)，所以总时间复杂度为 O(nmc)\mathcal{O}(nmc)。
CPP
#include <bits/stdc++.h>

using ll = long long;
constexpr ll mod = 1e9 + 7;

constexpr int maxn = 100 + 2;
constexpr int maxm = 10000 + 5;

ll binom[maxn][maxn];

inline void init() {
    for (int i = 0; i < maxn; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % mod;
        }
    }
}

int a[maxm], b[maxn], sum[maxm][maxn];
ll f[maxn][maxn], g[maxn][maxn];

inline void solve() {
    int n, c, m;
    scanf("%d%d%d", &n, &c, &m);
    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
        b[i] = std::count(a + 1, a + m + 1, i);
        if (b[i] > c) {
            return puts("0"), void();
        }
    }

    for (int i = 1; i <= m; i++) {
        memcpy(sum[i], sum[i - 1], sizeof(sum[i]));
        for (int j = 1; j <= a[i]; j++) {
            sum[i][j]++;
        }
    }

    memset(f, 0, sizeof(f)), f[1][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int p = 1; p <= (a[i] == 0 ? n : a[i]); p++) {
            for (int x = c; x >= 1; x--) {
                f[p][x] = f[p][x - 1];
            }
            f[p][0] = 0;
        }
        for (int p = (a[i] == 0 ? n : a[i]) + 1; p <= n + 1; p++) {
            memset(f[p], 0, sizeof(ll) * (c + 1));
        }
        for (int p = 1; p <= n; p++) {
            for (int x = b[p]; x <= c - sum[i][p + 1]; x++) {
                (f[p + 1][c - x] += f[p][c] * binom[c - sum[i][p]][x - b[p]]) %= mod;
            }
            f[p][c] = 0;
        }
    }

    printf("%lld\n", f[n + 1][0]);
}

int main() {
    init();
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...