A19505. 员工招聘（employ）
题目描述
员工招聘（employ）
题目描述
小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 ~ n。小 Z 和小 H 希望录用至少 m 人。
小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 1 ~ n 的排列 p，然后在第 i（1 ≤ i ≤ n）天通知编号为 pi 的人前来面试。
小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 i（1 ≤ i ≤ n）天的面试题的难度为 si ∈ {0,1}，其中 si = 0 表示这套题的难度较高，没有人能够做出；si = 1 表示这套题的难度较低，所有人均能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则则会录用。
然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 i（1 ≤ i ≤ n）的人的耐心上限可以用非负整数 ci 描述，若在他之前已经有不少于 ci 人被拒绝或放弃参加面试，则他也将放弃参加面试。
小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小 Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案对 998,244,353 取模后的结果。
输入格式
从文件employ.in中读入数据。
输入的第一行包含两个正整数 n, m，分别表示前来应聘的人数和希望录用的人数。
输入的第二行包含一个长度为 n 的字符串 s1 ... sn，表示每一天的面试题的难度。
输入的第三行包含 n 个非负整数 c1, c2, ..., cn，表示每个人的耐心上限。
输出格式
输出到文件employ.out中。
输出一行一个非负整数，表示能够录用至少 m 人的排列 p 的数量对 998,244,353 取模后的结果。
样例 1 输入
3 2
101
1 1 2样例 1 输出
2样例 1 解释
共有以下 2 种面试的顺序 p 能够让小 Z 和小 H 录用至少 2 人：
1. p = [1,2,3]，依次录用编号为 1 的人和编号为 3 的人；
2. p = [2,1,3]，依次录用编号为 2 的人和编号为 3 的人。
样例 2 输入
10 5
1101111011
6 0 4 2 1 2 5 4 3 3样例 2 输出
2204128样例 3
见选手目录下的 employ/employ3.in 与 employ/employ3.ans。
该样例满足测试点 6 ~ 8 的约束条件。
样例 4
见选手目录下的 employ/employ4.in 与 employ/employ4.ans。
该样例满足测试点 12 ~ 14 的约束条件。
样例 5
见选手目录下的 employ/employ5.in 与 employ/employ5.ans。
该样例满足测试点 18 ~ 21 的约束条件。
数据范围
对于所有测试数据，保证：
- 1 ≤ m ≤ n ≤ 500；
- 对于所有 1 ≤ i ≤ n，均有 si∈{0,1}；
- 对于所有 1 ≤ i ≤ n，均有 0 ≤ ci ≤ n。
特殊性质A:对于所有1 ≤i ≤ n,均有si=1。
特殊性质B:在s1,s2,...,sn中最多只有18个取值为1，即∑n i=1 si≤18。
参考答案
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=507,P=998244353;
ll fac[N];
ll n,m,c[N],sum[N],k,w[N],ans; int dp[N][N][N];
char s[N];
void mian() {
fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
scanf("%lld%lld%s",&n,&m,s+1);
for (ll i=1;i<=n;i++) if (s[i]-'0'==1) k++,w[k]=i-k;
if (!k) return cout<<"0",void();
for (ll i=1;i<=n;i++) scanf("%lld",&c[i]),sum[c[i]]++;
for (ll i=1;i<=n;i++) sum[i]+=sum[i-1];
dp[0][0][0]=1;
for (ll i=1,o=1;i<=k;i++) for (ll x=0;x<i;x++) for (ll y=0;x+y<i;y++) {
(dp[i][x+1][y]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定第 i 个人走
(dp[i][x][y+1]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定他没走，容斥它
(dp[i][x][y]+=dp[i-1][x][y])%=P; // 指定他没走，不容斥它
}
for (ll x=0;x<=k-m;x++) for (ll y=0;x+y<=k;y++)
(ans+=(y&1?P-1:1)*dp[k][x][y]%P*fac[n-x-y])%=P;
cout<<ans;
}
bool ORY; int main() {
// while (1)
// int t; for (scanf("%d",&t);t--;)
mian();
cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
return 0;
}