P14364 [CSP-S 2025] 员工招聘 / employ

· · 题解

我场上最后 30min 想到了的！！！但是一堆分讨没时间了/ll

思路：

你发现排列的计数，一般状态是重点；这题对排列的限制在 c 这里，于是考虑把 c 这个东西压进状态里。

于是想到 dp_{i, j, k} 表示考虑前 i 天，前面有 j 个人 fail 了，然后其中有 k 个人 c > j 的方案数（此时这些人具体是谁是没有必要的，因为只要他的 c > j 就不会造成影响），于是前面 i 天选了 i - k 个 c \le j 的，进行分讨（这里设 w_i 表示 c 等于 i 的人的数量，s_i 表示 c 小于等于 i 的人的数量）：

  1. 否则放一个 c > j 的人来，于是 j 不变，k 加一：

    dp_{i - 1, j, k} \to dp_{i, j, k + 1}
    • 若 s_i = 0：

  2. 此时随便放一个都是 fail，所以 j \gets j + 1，同时也要枚举前面恰好选了 l 个 c 是 j + 1 的，于是考虑若放 c \le j + 1 进来，方案数是 s_{j + 1} - i + k + 1 - l：

    dp_{i - 1, j, k} (s_{j + 1} - i + k + 1 - l) \binom{w_{j + 1}}{k} \binom{k}{l} l! \to dp_{i, j + 1, k - l}

  3. 若是放 c > j + 1 进来，则 k 要多加 1：

dp_{i - 1, j ,k} \binom{w_{j + 1}}{k} \binom{k}{l} l ! \to dp_{i, j + 1, k - l + 1}

你发现所有枚举的 \sum l = n，于是时间复杂度是 O(n^3) 的。

完整代码：

#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 505, mod = 998244353;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, ans;
int dp[N][N][N], w[N], s[N], C[N][N], fac[N];
char op[N];
int c[N];
inline void getadd(int &x, int y){
    x = (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline int add(int x, int y){
    return (x + y >= mod) ? (x + y - mod) : (x + y);
}
bool End;
int main(){
    n = read(), m = read();
    scanf("%s", op + 1);
    for(int i = 1; i <= n; ++i){
        c[i] = read();
        ++w[c[i]];
    }
    fac[0] = 1;
    s[0] = w[0];
    for(int i = 1; i <= n; ++i){
        s[i] = s[i - 1] + w[i];
        fac[i] = 1ll * fac[i - 1] * i % mod;
//      cerr << s[i] << ' ';
    }
    for(int i = 0; i <= n; ++i){
        C[i][0] = 1;
        for(int j = 1; j <= i; ++j)
          C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= i - 1; ++j){
            for(int k = 0; k <= i - 1; ++k){
                if(!dp[i - 1][j][k])
                  continue;
//              cerr << "Yes\n" << ' ' << i - 1 << ' ' << j << ' ' << k << ' ' << dp[i - 1][j][k] << '\n';
                if(op[i] == '1'){
//                  if(s[j] != n)
//                  cerr << i << ' ' << j << ' ' << k + 1 << '\n';
                    getadd(dp[i][j][k + 1], dp[i - 1][j][k]);
                    if(s[j] - i + k + 1 < 0)
                      continue;
                    for(int l = 0; l <= min(k, w[j + 1]); ++l)
                      getadd(dp[i][j + 1][k - l], 1ll * dp[i - 1][j][k] * (s[j] - i + k + 1) % mod * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
                }
                else{
                    for(int l = 0; l <= min(k, w[j + 1]); ++l){
//                      if(s[j + 1] != n)
                        getadd(dp[i][j + 1][k - l + 1], 1ll * dp[i - 1][j][k] * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
                        if(s[j + 1] - i + k + 1 - l > 0)
                          getadd(dp[i][j + 1][k - l], 1ll * dp[i - 1][j][k] * (s[j + 1] - i + k + 1 - l) % mod * C[w[j + 1]][l] % mod * C[k][l] % mod * fac[l] % mod);
                    }
                }
            }
        }
    }
    for(int i = 0; i <= n - m; ++i)
      getadd(ans, 1ll * fac[n - s[i]] * dp[n][i][n - s[i]] % mod);
    write(ans);
//chrr << '\n' << abs(&Bhgin - &End) / 1048576 << "MB";
    return 0;
}