【写于2026-02-21】【搬运于2026-5-2】
太深刻了。看了很多次题解尝试理解都失败了。算是记录一些之前没想通的点吧。
参考：https://www.luogu.com.cn/article/6jgvpe05 ，第一篇 jiangly 的题解和这篇本质上思路一致。
首先明确题意：每天题目难度已定，但面试的人可以任意排序。
对于难题对应天，一定是无法面试通过的。而对应简单题的天，有两种情况：
- 耐心足够，面试通过
- 耐心不够，自己跑了
我们只对简单题对应天进行决策面试人要不要通过。对于已重排顺序后的第 \(i\) 个人，若他的忍耐值为 \(v_{i}\)（原序列中的某个 \(c_i\)），设前 \(i-1\) 个人走了 \(t_i\) 个，那么这个人会在 \(v_i\le w_i+t_i\) 时走掉。\(w_i\) 是这个 \(s_i=1\) 在原串中前面 \(0\) 的个数，表示因为难题而强制走掉的人。以下讨论的“人”和面试是否通过，未特殊说明默认为简单题对应天。记简单天数为 \(k\) 天。
\(m=1\) 的情况看上面的题解。
我们尝试去分别计算每个走人情况被多少排列方案取到，即把答案表示成 \(ans = \sum_{i=0}^{k-m} g_i\)，\(g_i\) 表示 \(i\) 个人通过面试。这样 \(t_i\) 可以当做定值，会好处理得多。可以认为，这里的 \(i\) 表示的是 dp 状态中的第二维 \(x\)。
对于一个 \(i\)，如果我们指定他走，那么 \(v_i\) 就要 \(\le w_i+t_i\)。否则需要 \(>w_i+t_i\)。出现了两个方向，不好处理。我们发现，\(v_i\le w_i+t_i\) 因为满足单调性所以计数较为简单（\(w_i\) 单增，\(t_i\) 也单增）。所以考虑将 \(v_i\le w_i+t_i\) 作为容斥的钦定条件，没有钦定的天数不受限制，我们最后需要容斥出除了选中的 \(x\) 天，没有其他天满足 \(v_i\le w_i+t_i\)。 于是就有了 dp 的第三维 \(y\)，表示钦定的不属于选中的 \(x\) 天但满足 \(v_i\le w_i+t_i\) 的天数。
梳理一下，状态转移有三种：
- 第 \(i\) 个人耐心不够走了，对第二维有贡献
或者第 \(i\) 个人没走：
- 钦定第 \(i\) 个人耐心不够但没走，是不合法方案，对第三维有贡献，之后是要被容斥掉的。
- 不管第 \(i\) 个人耐心够不够，不钦定容斥它。
本题的 dp 是对子问题的容斥。意思是，容斥是为了求出子问题的答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 510;
const int p = 998244353;
char s[N];
int c[N],sum[N],w[N],f[N][N][N],fac[N];
void add(int &x,int y){x += y;if(x >= p)x -= p;
}
signed main(){int n,m,k = 0;scanf("%lld%lld",&n,&m);scanf("%s",s + 1);fac[0] = 1;for(int i = 1; i <= n; i++){scanf("%lld",&c[i]);sum[c[i]]++;if(s[i] == '1')k++,w[k] = i - k;//第k0个可通过面试题前面有w[k0]套不可通过面试题 fac[i] = fac[i - 1] * i % p;//阶乘 }for(int i = 1; i <= n; i++)sum[i] += sum[i - 1];//忍耐度小于i的人数f[0][0][0] = 1;
// for(int i = 1; i <= k; i++){//考虑可能出现决策的k天，有忍耐度不够/面试过了两种情况 for(int x = 0; x < i; x++){for(int y = 0; x + y < i; y++){add(f[i][x + 1][y],f[i - 1][x][y] * max(sum[w[i] + x] - x - y,0 * 1ll) % p);//第i个人忍耐度不够走了 add(f[i][x][y + 1],f[i - 1][x][y] * max(sum[w[i] + x] - x - y,0 * 1ll) % p);//第i个人面试过了，且容斥这个人 add(f[i][x][y],f[i - 1][x][y]);//第i个人面试过了，且不容斥这个人 }}}int ans = 0;for(int i = 0; i <= k - m; i++){//i个人明确拒绝，不能超过k-m个 for(int j = 0; i + j <= k; j++){//对j进行容斥 int x = (j & 1) ? (p - 1) : 1;add(ans,x * f[k][i][j] % p * fac[n - i - j] % p);}}printf("%lld",ans);return 0;
}
//https://www.luogu.com.cn/article/6jgvpe05