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

liujiaxi123456 · 2025-11-05 22:15:55 · 题解

大体思路：

显然是 DP，把 c_i 排序后，状态大概就是 s 一维，c 一维，录用了多少人一维。

贡献延迟计算。

具体思路：

先设 f_{i, j} 表示前 i 个人，录用了 j 个人，我们令 d = i-j（即耐心的阈值）。

显然转移不了，原因是不知道还剩哪些 c 可以用，哪些不能用。

考虑怎么记：

• 影响的显然是 \le d 和 > d 的数量。
• 由于 d 不减，所以显然记录 \le d 的数量。

分析一下转移时的限制：

• 若 s_i=0：必然无法录用。
• 若 s_i=1：
  • 若 c_i\le d：无法录用。
  • 否则可以。

发现直接转移的主要问题在于当 d\leftarrow d+1 时，c = d+1 的部分的数量不好计算。

因此，如果每次都把 i 的贡献直接钦定好在上述情况下显然是不行的。

考虑贡献延迟计算：

• 最直接的思路就是在 d\leftarrow d+1 时，枚举 c=d+1 的数量转移。
• 由于对于同样的 i,k，这样是 \sum cnt_j 的，所以是 O(n^3) 的。

但这样转移非常复杂，考虑有没有简洁一点的做法：

• 发现主要是录用不好转移，考虑容斥，用 c 没有限制的情况减去 c_i\le d 的。

• 这样 s_i=1 的情况就分为三种：

  • 使用 c_i\le d，且不录用，这个贡献可以直接算。
  • 使用 c_i\le d，但录用，这个贡献也可以直接算（注意贡献是负的）。
  • 使用 c_i> d，录用，贡献没法直接算，记到后效性里面，贡献延迟计算。

• 于是设 f_{i, j, k} 表示前 i 个人，录用了 j 个人，前 i 个中有 k 个贡献已经算好了。

考虑转移：

• 考虑从前向后转移。
• - 直接 $f_{i, j, k} \rightarrow f_{i+1, j, k}$。
• - 不录用： - $f_{i, j, k}\cdot (all(i-j)-k)\rightarrow f_{i+1, j, k+1}
  • 录用，且合法：
  • f_{i, j, k}\rightarrow f_{i+1, j+1, k}
  • 录用，但不合法：
  • f_{i, j, k}\cdot -(all(i-j)-k)\rightarrow f_{i+1, j+1, k+1}

统计答案：

• ans = \sum_{j=m}^n\sum_{k=0}^nf_{n, i, k}\cdot (n-k)!
• 比较显然吧，就是还有 n-k 个贡献没有钦定，剩下的直接排列即可。

Code：

#include<bits/stdc++.h>
using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t;
#define ll long long
using namespace std;

const int Maxn = 505;
const ll MOD = 998244353;

namespace Josh_zmf {

    int N, M, all[Maxn], f[Maxn][Maxn][Maxn]; string s; ll fac[Maxn];

    inline int main() {
        cin>> N>> M>> s, s = ' ' + s;
        for(int i=1, x; i<=N; i++)  cin>> x, all[x]++;
        for(int i=1; i<=N; i++) all[i] += all[i-1];
        f[0][0][0] = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<=i; j++) {
                for(int k=0; k<=i; k++) {
                    if(s[i+1] == '0') {
                        f[i+1][j][k] = f[i][j][k];
                    } else {
                        f[i+1][j+1][k] = (f[i+1][j+1][k] + f[i][j][k]) %MOD;
                        if(all[i-j]-k > 0) {
                            f[i+1][j+1][k+1] = (f[i+1][j+1][k+1] + -1ll*f[i][j][k]*(all[i-j]-k)) %MOD;
                            f[i+1][j][k+1] = (f[i+1][j][k+1] + 1ll*f[i][j][k]*(all[i-j]-k)) %MOD;
                        }
                    }
                }
            }
        }
        fac[0] = 1;
        for(int i=1; i<=N; i++) fac[i] = fac[i-1]*i %MOD;
        ll ans = 0;
        for(int j=M; j<=N; j++) {
            for(int k=0; k<=N; k++) ans += f[N][j][k]*fac[N-k] %MOD;
        }
        cout<< (ans%MOD+MOD)%MOD<< '\n';
        return 0;
    }

} bool ED;

signed main() {
#if defined(ONLINE_JUDGE) && ONLINE_JUDGE == 1

#elif defined(Debugging)
    freopen("../__IO__/NAME.in", "r", stdin);
#elif !defined(LOCAL)
    freopen("NAME.in", "r", stdin);
    freopen("NAME.out", "w", stdout);
#else
    // freopen("../__IO__/NAME.in", "r", stdin);
    // freopen("../__IO__/NAME.out", "w", stdout);
#endif
    int st = clock(); Josh_zmf::main();
#ifndef Debugging
    cerr<< "time:: "<< clock()-st<< "ms\n";
    cerr<< "Static Memory:: "<< (int)(abs(&ST-&ED)/1024./1024)<< "MB\n";
#endif
    return 0;
}