公式多

解析

令 $(h_i)$( 表示前 $i$ 天中，难度较高的天数的数量。令 $(f_i)$ 表示 $(c_j)$ 小于等于 $i$ 的 $j$ 的数量。我们考虑对于难度较高的天，先不分配具体是谁参加面试。最后答案乘以 $(h_n!)$ 即可。令 $(g_{i, j, k})$ 表示前 $i$ 天中，有 $j$ 天是不录用人的，且剩下 $(i-j)$ 天中有 $k$ 天是没有确定具体是谁去面试的方案数。我们称 $(c_k \leq j)$ 的人为 “弱人”，其它人为 “强人”。若 $(s_{i + 1} = 0)$，$(g_{i + 1, j + 1, k - l} += g_{i, j, k} * \binom{c_{j + 1} - c_{j}}{l} * \binom{k}{l} * l!)$。若 $(s_{i + 1} = 1)$，且下一天录用人，$(g_{i + 1, j, k + 1} += g_{i, j, k})$ 。若 $(s_{i + 1} = 1)$，且下一天不录用人， $(g_{i + 1, j + 1, k - l} += g_{i, j, k} * (f_j - (j - h_i)) * \binom{c_{j + 1} - c_j}{l} * \binom{k}{l} * l!)$。时间复杂度 $(O(n^3))$。

答案

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;

template <int P>
struct ModInt {
    int x;
    static int shift(int x) {
        while (x < 0) x += P;
        while (x >= P) x -= P;
        return x;
    }
    ModInt(int x = 0) : x(shift(x)) {}
    ModInt& operator+=(const ModInt &other) {
        if ((x += other.x) >= P) x -= P;
        return *this;
    }
    ModInt& operator-=(const ModInt &other) {
        if ((x -= other.x) < 0) x += P;
        return *this;
    }
    ModInt& operator*=(const ModInt &other) {
        x = (ll)x * other.x % P;
        return *this;
    }
    friend ModInt operator+(ModInt a, const ModInt &b) {
        return a += b;
    }
    friend ModInt operator-(ModInt a, const ModInt &b) {
        return a -= b;
    }
    friend ModInt operator*(ModInt a, const ModInt &b) {
        return a *= b;
    }
    ModInt pow(ll exp) const {
        ModInt res = 1, base = *this;
        while (exp) {
            if (exp & 1) res = res * base;
            base = base * base;
            exp >>= 1;
        }
        return res;
    }
    ModInt inv() const {
        return pow(P - 2);
    }
};
using Mint = ModInt<P>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    string s;
    cin >> n >> m >> s;
    vector<int> cnt(n + 1);
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        ++cnt[x];
    }
    for (int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
    }
    vector<vector<vector<Mint>>> f(n + 1, vector<vector<Mint>>(n + 1, vector<Mint>(n + 1, Mint(0))));
    f[0][0][0] = 1;
    // i = n days
    // j = failed people
    // k = succeed non filled people
    // candidate = cnt[j] - (j - c0) - (n - j - k)
    vector<Mint> fct(n + 1, 1), ifc(n + 1);
    for (int i = 1; i <= n; i++) {
        fct[i] = fct[i - 1] * i;
    }
    ifc[n] = fct[n].inv();
    for (int i = n - 1; i >= 0; i--) {
        ifc[i] = ifc[i + 1] * (i + 1);
    }
    auto C = [&](int a, int b) -> Mint {
        if (b < 0 || b > a) return 0;
        return fct[a] * ifc[b] * ifc[a - b];
    };
    int c0 = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            for (int j = c0; j <= i; j++) {
                int x = cnt[j + 1] - cnt[j];
                Mint pl = fct[x];
                for (int k = 0; k <= i - j; k++) {
                    for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
                        f[i + 1][j + 1][k - z] += f[i][j][k] * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
                    }
                }
            }
            c0++;
        } else {
            for (int j = c0; j <= i; j++) {
                for (int k = 0; k <= i - j; k++) {
                    // not succeed
                    int candidate = cnt[j] - (j - c0) - (i - j - k);
                    if (candidate > 0) {
                        for (int z = 0; z <= cnt[j + 1] - cnt[j] && z <= k; z++) {
                            f[i + 1][j + 1][k - z] += f[i][j][k] * candidate * C(k, z) * C(cnt[j + 1] - cnt[j], z) * fct[z];
                        }
                    }
                    // succeed
                    if (k + 1 <= n) {
                        f[i + 1][j][k + 1] += f[i][j][k];
                    }
                }
            }
        }
    }
    Mint ans = 0;
    for (int j = 0; j <= n - m; j++) {
        for (int k = 0; k <= n; k++) {
            if (n - cnt[j] >= k) {
                ans += f[n][j][k] * C(n - cnt[j], k) * fct[k];
            }
        }
    }
    ans *= fct[c0];
    cout << ans.x << "\n";
    return 0;
}