题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

讲一下 jiangly 的做法。

我们假设已经钦定好了每天的人是否录取，设

x_i

表示前缀没录取的总人数。

考察第

i

天的情况：

$s_i=0$ ，一定不录取，任意放人都可以。
$s_i=1$ $s_{i} = 1$ ，分讨是否录取：
- 录取，要求 $c>x_i$ 。
- 不录取，要求 $c\le x_i$ 。

这个

c>x_i

有点烦，让我们把它容斥成「任意

{}-[c\le x_i]

」。

设

f_{i,j,k}

表示前

i

个人，拒绝了

j

个人，钦定了

k

个人的总方案，转移只需要根据前面算一下就好了，是 3d-0d 的。统计答案也是简单的，时间复杂度

\mathcal O(n^3)

。

Code 已过民间数据

CPP

int n, m;
char s[N];
int a[N];
Z f[N][N][N];
Z fac[N], inv[N];

void mslv() {
    rd(n, m), rd(s + 1);
    rep(i, 1, n) a[r32]++;
    rep(i, 1, n) a[i] += a[i - 1];
    f[0][0][0] = 1;
    req(i, 0, n) {
        if (s[i + 1] == '0') rep(j, 0, i) rep(k, 0, i)
            f[i + 1][j + 1][k] += f[i][j][k];
        else rep(j, 0, i) rep(k, 0, i) {
            f[i + 1][j][k] += f[i][j][k];
            Z x = a[j] - k;
            f[i + 1][j][k + 1] -= x * f[i][j][k];
            f[i + 1][j + 1][k + 1] += x * f[i][j][k];
        }
    } Z ans;
    rep(j, 0, n - m) rep(k, 0, n) ans += f[n][j][k] * fac[n - k];
    prs(ans);
}

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）

文章操作

相关推荐

评论

题解：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据）