《容斥基础练习》

题意：

给定长度为 $n$ 的 $01$ 串：

• $1$ 的位置可以录取人
• $0$ 的位置一定不能录取人

共有 $n$ 个人，第 $x$ 个人忍耐度为 $c_x$。为所有人分配应聘顺序：若某人在应聘时，前方录取失败人数超过 $c_x$，则他一定不会被录取。

求所有方案中，录取人数超过 $m$ 的方案数。

思路：

预处理：只考虑 $1$ 位置

$0$ 位置对“能否录取”不产生可控贡献（必失败），可用“特殊元素优先处理”：

1. 先把所有 $1$ 位置安排并计数；
2. 剩下的位置再乘上排列数补回。

下文“位置”均指 $1$ 的位置。

定义：

• $w_i$：前 $i$ 个字符中 $0$ 的个数
• $t_i$：前 $i$ 个字符中，有多少个 $1$ 位置最终无法录取
• $v_i$：第 $i$ 个位置能录取所需的最小忍耐度

则：

$$v_i=t_i+w_i$$

---

Step 1：先看 $m=1$

当“录取人数超过 $1$”，可先算“全都录取不了”的方案数 $res$，再做：

$$ans = |\Omega| - res,\qquad |\Omega|=n!$$

令计数函数：

$$S(p)=\left|\{x\mid c_x\le p\}\right|$$

若记第 $r$ 个 $1$ 的原下标为 $pos_r$，则“全不录取”的乘法计数可写成类似：

$$res=\prod_{r=1}^{k}\left(S(pos_r-1)-(r-1)\right)$$

其中 $k$ 为 $1$ 的总数。

---

Step 2：出现反向限制，用容斥统一方向

枚举某个状态 $s$（二进制表示哪些 $1$ 位置录取）：

• 若位置录取：要求 $v_i \le c_x$
• 若位置不录取：要求 $v_i > c_x$

两类条件方向相反，直接计数困难。定义事件 $A_i$：位置 $i$ “无法录取”。则需求为：

$$\left|\bigcap_{i\in s}\overline{A_i}\right|$$

利用补集与容斥：

$$\left|\bigcap_{i\in s}\overline A_i\right| = |\Omega|-\left|\bigcup_{i\in s}A_i\right|$$

注意空集合 $T=\varnothing$ 时：

$$\bigcap_{i\in \varnothing} A_i = \Omega$$

并写成标准容斥形式（含空集）：

$$\left|\bigcap_{i\in s}\overline{A_i}\right| = \sum_{T\subseteq s}(-1)^{|T|} \left|\bigcap_{i\in T}A_i\right|$$

做法：对每个状态 $s$，枚举其子集 $T$，计算 $\left|\bigcap_{i\in T}A_i\right|$ 并按 $(-1)^{|T|}$ 加减。

---

Step 3：把重复的子集枚举用 DP 计算

在 Step 2 中，很多量会被重复计算，因此用 DP 代替“对每个 $s$ 枚举所有 $T$”。

示例状态：

$$dp_{i,j,k}: \text{前 } i \text{ 个 } 1 \text{ 中，} j \text{ 个钦定不录取，} k \text{ 个因容斥而不录取}$$

把容斥求和结构嵌入 $dp$ 递推即可。

//
// Created by EDY on 2025/12/12.
//
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 998244353;
vector< vector< int > > dp(505 , vector< int >(505 , 0));
int n , m;
void solve1() {
    //m = 1
    /*
        此时，考虑容斥，即求出所有人都不录取的情况
        依次枚举原串当中的每一个1
    */
    string s;
    cin >> s;
    vector<int>arr(n + 5 , 0);
    vector<int>pre(n + 5 , 0);
    s = '#' + s;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> arr[i];
        pre[arr[i]]++;
    }
    for (int i = 1 ; i <= n ; i ++) {
        pre[i] += pre[i - 1];
    }
    int ans = 1;
    for (int i = 1 ; i <= n ; i ++) {
        ans *= i;
        ans %= Mod;
    }
    int del = 1;
    int k = 0;
    int p = 0;
    for (int i = 1 ; i <= n ; i ++) {
        if (s[i] == '0') {
            k++;
            del *= k;
            del %= Mod;
        }
        else {
            //此时, 前面走了i-1个人 ， 那么vi需要 < i - 1
            del *= (pre[i - 1] - p);
            p++;
            del %= Mod;
        }
    }
    ans -= del;
    ans += Mod;
    ans %= Mod;
    cout << ans << endl;
}
void solve2() {
    /*
        收到solve1的启发，我们会发现，我们可以枚举的是每一种走人的方案
        然后此时每个1的限制就会确定下来，会好算很多

        对于每一个1，如果我需要走，需要c < k + p
        如果不让这个位置走，需要c >= k + p
        这是两个完全相反的东西，所以我们考虑容斥
    */
    string s;
    cin >> s;
    vector<int>arr(n + 5 , 0);
    vector<int>pre(n + 5 , 0);
    vector<int>fac(n + 5 , 0);
    s = '#' + s;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> arr[i];
        pre[arr[i]]++;
    }
    for (int i = 1 ; i <= n ; i ++) {
        pre[i] += pre[i - 1];
    }
    fac[0] = 1;
    for (int i = 1 ; i <= n ; i ++) {
        fac[i] = fac[i - 1] * i;
        fac[i] %= Mod;
    }
    int ans = 0;
    int k = 0 , p = 0;
    vector<int>pos;
    for (int i = 1 ; i <= n ; i ++) {
        if (s[i] == '0') {
            p++;
        }
        else {
            k++;
            pos.push_back(i);
        }
    }
    for (int i = 0 ; i < (1 << k) ; i ++) {
        //枚举每一个位置
        int cnt = 0;
        if (__builtin_popcountll(i) < m) continue;
        for (int t = i ; ; t = (t-1) & i) {
            //枚举所有i的子集
            int rw = 1 , x = 0 , y = 0;
            //y -> 已经拿掉的
            for (int j = 0 ; j < k ; j ++) {
                if (i >> j & 1) {
                    if (t >> j & 1) {
                        //这个位置是取不到的
                        long long idx = pos[j] - 1 - (j - x);
                        if (idx < 0) idx = 0;
                        if (idx > n) idx = n;
                        long long val = pre[idx] - x - y;
                        rw = rw * max(0LL, val) % Mod;
                        y++;
                    }
                    else {
                        //取什么无所谓
                    }
                }
                else {
                    //这个位置必须取不到
                    long long idx = pos[j] - 1 - (j - x);
                    if (idx < 0) idx = 0;
                    if (idx > n) idx = n;
                    long long val = pre[idx] - x - y;
                    rw = rw * max(0LL, val) % Mod;
                    x++;
                }
            }
            rw *= (y & 1LL ? Mod - 1 : 1LL);
            rw %= Mod;
            rw *= fac[n - x - y];
            rw %= Mod;
            cnt += rw;
            cnt %= Mod;
            if (t == 0) {
                break;
            }
        }
        ans += cnt;
        ans %= Mod;
    }
    cout << ans << endl;
}
void solve3() {
     /*
        solve2很多地方都是属于可重复计算问题，因此考虑dp优化
    */
    string s;
    cin >> s;
    vector<int>arr(n + 5 , 0);
    vector<int>pre(n + 5 , 0);
    vector<int>fac(n + 5 , 0);
    s = '#' + s;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> arr[i];
        pre[arr[i]]++;
    }
    for (int i = 1 ; i <= n ; i ++) {
        pre[i] += pre[i - 1];
    }
    fac[0] = 1;
    for (int i = 1 ; i <= n ; i ++) {
        fac[i] = fac[i - 1] * i;
        fac[i] %= Mod;
    }
    int ans = 0;
    int k = 0 , p = 0;
    vector<int>pos;
    for (int i = 1 ; i <= n ; i ++) {
        if (s[i] == '0') {
            p++;
        }
        else {
            k++;
            pos.push_back(i);
        }
    }
   // memset(dp , 0 , sizeof dp);
    dp[0][0] = 1;
    for (int i = 1 ; i <= k ; i ++) {
        vector< vector< int > > ndp(505 , vector<int>(505 , 0));
        for (int x = 0 ; x < i ; x ++) {
            for (int y = 0 ; x + y < i ; y ++) {
                ndp[x + 1][y] += dp[x][y] * max(pre[pos[i - 1] - i + x] - x - y, 0LL) % Mod;
                ndp[x + 1][y] %= Mod;
                ndp[x][y + 1] += dp[x][y] * max(pre[pos[i - 1] - i + x] - x - y , 0LL) % Mod;
                ndp[x][y + 1] %= Mod;
                ndp[x][y] += dp[x][y];
                ndp[x][y] %= Mod;
            }
        }
        dp = ndp;
    }
    if(k - m < 0){
    	cout << 0 << endl;
    	return;
    }
    for (int x = 0 ; x <= k - m ; x ++) {
        for (int y = 0 ; x + y <= k ; y ++) {
            ans += (y & 1 ? Mod - 1 : 1) * dp[x][y] % Mod * fac[n - x - y] % Mod;
            ans %= Mod;
        }
    }
    cout << ans << endl;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    if (m == 1) {
        solve1();
    }
    else {
        solve3();
    }
}