记录编号	609311	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4199.[CSP-S 2025 T4]员工招聘	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	3.789 s
提交时间	2025-11-06 20:07:18	内存使用	7.81 MiB

#include<bits/stdc++.h>
using namespace std;
#define LOCAL
#define ll long long
#define db double
#define Ciallo true
#define pir pair <ll,ll>
#define fs first
#define sc second
#define MAXN 510
#define mod 998244353
#define add(x, y) x = (x + y) % mod
inline ll read(){
    ll f = 1, num = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c=='-') f = -1;c = getchar();
    }
    while(c>='0'&&c<='9') num = num * 10 + c - '0', c = getchar();
    return num * f;
}

ll f[2][MAXN][MAXN];
int cnt[MAXN],pre[MAXN];
int c[MAXN];
char s[MAXN];
int n,m;

ll fac[MAXN], inv[MAXN];
ll C(int x, int y){
    return fac[x] * inv[y] % mod * inv[x - y] % mod;
}

ll P(int x, int y){
    return fac[x] * inv[x - y] % mod;
}

ll fpow(ll bas, ll ex = mod - 2){
    ll ret = 1;
    while(ex){
        if(ex & 1)ret = ret * bas % mod;
        bas = bas * bas % mod;
        ex >>= 1;
    }
    return ret;
}

int main(int argc, char* argv[]){
    #ifdef FS
        freopen(argv[1], "r", stdin);
        freopen(argv[2], "w", stdout);
    #elif defined(LOCAL)
        freopen("employ.in", "r", stdin);
        freopen("employ.out", "w", stdout);
    #endif

    n = read(), m = read();

    fac[0] = 1;
    for(int i = 1;i <= n; ++i)fac[i] = fac[i - 1] * i % mod;
    inv[n] = fpow(fac[n]);
    for(int i = n - 1;i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % mod;

    for(int i = 1;i <= n; ++i)cin >> s[i];
    cerr << (s + 1) << endl;
    for(int i = 1;i <= n; ++i){
        c[i] = read();
        cnt[c[i]] ++;
    }
    pre[0] = cnt[0];
    for(int i = 1;i <= n; ++i){
        pre[i] = pre[i - 1] + cnt[i];
    }

    // for(int i = 1; i <= n; ++i){
        // cout << fac[i] << " ";
        // for(int j = 1;j <= i; ++j)cout << C(i, j) << " ";
        // cout << endl;
    // }
    // cout << endl;

    f[0][0][0] = 1;
    for(int i = 0;i < n; ++i){
        memset(f[(i + 1) & 1], 0, sizeof(f[(i + 1) & 1]));
        for(int j = 0;j <= i; ++j){
            for(int k = 0;k <= i; ++k){
                if(!f[i & 1][j][k])continue;
                if(k > n - pre[j] || i - k > pre[j])continue;
                // cout << i << " " << j << " " << k << " " << f[i & 1][j][k] << endl;
                if(s[i + 1] == '0'){
                    //  选了一个 <= j 的数
                    for(int u = 0;u <= min(cnt[j + 1], k); ++u){// 枚举之前选了多少个 j + 1
                        add(f[(i + 1) & 1][j + 1][k - u], f[i & 1][j][k] * (pre[j] - (i - k)) % mod * P(cnt[j + 1], u) % mod * C(k, u) % mod);
                    }

                    // 选了一个 > j + 1 的值
                    for(int u = 0;u <= min(cnt[j + 1], k); ++u){
                        add(f[(i + 1) & 1][j + 1][k - u + 1], f[i & 1][j][k] * P(cnt[j + 1], u) % mod * C(k, u) % mod);
                    }

                    // 恰好选了 j + 1
                    for(int u = 0;u <= min(cnt[j + 1] - 1, k); ++ u){
                        add(f[(i + 1) & 1][j + 1][k - u], f[i & 1][j][k] * P(cnt[j + 1], u + 1) % mod * C(k, u) % mod);
                    }
                }else{
                    // 选了一个 <= j 的数
                    for(int u = 0;u <= min(cnt[j + 1], k); ++u){
                        add(f[(i + 1) & 1][j + 1][k - u], f[i & 1][j][k] * (pre[j] - (i - k)) % mod * P(cnt[j + 1], u) % mod * C(k, u) % mod);
                    }

                    // 选了一个 >= j + 1 的值
                    add(f[(i + 1) & 1][j][k + 1], f[i & 1][j][k]);
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 0;i <= n - m; ++i){// 拒绝了多少人
        // cerr << i << " " << f[n & 1][i][n - pre[i]] << endl;
        add(ans, f[n & 1][i][n - pre[i]] * fac[n - pre[i]] % mod);
    }
    cout << ans << endl;

    cerr << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";
    return 0;
}