ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5056: 员工招聘

内存限制：512 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：2 通过：1
提交提交记录统计Web Board

题目描述

小 Z 和小 H 想要合伙开一家公司，共有 $n$ 人前来应聘，编号为 $1 \sim n$。小 Z 和小 H 希望录用至少 $m$ 人。

小 H 是面试官，将在接下来 $n$ 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 $1 \sim n$ 的排列 $p$，然后在第 $i$ ($1 \leq i \leq n$) 天通知编号为 $p_i$ 的人前来面试。

小 H 准备了 $n$ 套难度不一的面试题。由于 $n$ 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 $i$ ($1 \leq i \leq n$) 天的面试题的难度为 $s_i \in \{0,1\}$，其中 $s_i = 0$ 表示这套题的难度较高，没有人能够做出；$s_i = 1$ 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 $i$ ($1 \leq i \leq n$) 的人的耐心上限可以用非负整数 $c_i$ 描述，若在他之前已经有**不少于** $c_i$ 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 $p$ 能够让他们录用至少 $m$ 人。你需要帮助小 Z 求出，能够录用至少 $m$ 人的排列 $p$ 的数量。由于答案可能较大，你只需要求出答案对 $998\,244\,353$ 取模后的结果。

## 输入格式

输入的第一行包含两个正整数 $n, m$，分别表示前来应聘的人数和希望录用的人数。

输入的第二行包含一个长度为 $n$ 的字符串 $s_1 \dots s_n$，表示每一天的面试题的难度。

输入的第三行包含 $n$ 个非负整数 $c_1, c_2, \dots, c_n$，表示每个人的耐心上限。

## 输出格式

输出一行一个非负整数，表示能够录用至少 $m$ 人的排列 $p$ 的数量对 $998\,244\,353$ 取模后的结果。

## 输入输出样例 #1

### 输入 #1

```
3 2
101
1 1 2
```

### 输出 #1

```
2
```

## 输入输出样例 #2

### 输入 #2

```
10 5
1101111011
6 0 4 2 1 2 5 4 3 3
```

### 输出 #2

```
2204128
```

## 说明/提示

### 【样例 1 解释】

共有以下 2 种面试的顺序 $p$ 能够让小 Z 和小 H 录用至少 2 人:

1. $p = [1,2,3]$, 依次录用编号为 1 的人和编号为 3 的人;
2. $p = [2,1,3]$, 依次录用编号为 2 的人和编号为 3 的人。

### 【样例 3】

见选手目录下的 $\textbf{\textit{employ/employ3.in}}$ 与 $\textbf{\textit{employ/employ3.ans}}$。

该样例满足测试点 6 ~ 8 的约束条件。

### 【样例 4】

见选手目录下的 $\textbf{\textit{employ/employ4.in}}$ 与 $\textbf{\textit{employ/employ4.ans}}$。

该样例满足测试点 12 ~ 14 的约束条件。

### 【样例 5】

见选手目录下的 $\textbf{\textit{employ/employ5.in}}$ 与 $\textbf{\textit{employ/employ5.ans}}$。

该样例满足测试点 18 ~ 21 的约束条件。

### 【数据范围】

对于所有测试数据，保证:
- $1 \leq m \leq n \leq 500$;
- 对于所有 $1 \leq i \leq n$，均有 $s_i \in \{0,1\}$;
- 对于所有 $1 \leq i \leq n$，均有 $0 \leq c_i \leq n$。

::cute-table{tuack}

| 测试点编号 | $n \leq$ | $m$ | 特殊性质 |
| :--: | :--: | :--: | :--: |
| $1,2$ | $10$ | $\leq n$ | 无 |
| $3 \sim 5$ | $18$ |  ^ | ^ |
| $6 \sim 8$ | $10^2$ | ^ | A |
| $9 \sim 11$ | ^ | ^ | 无 |
| $12 \sim 14$ | $500$ | $=1$ | ^ |
| $15$ | ^ | $=n$ | ^ |
| $16,17$ | ^ | $\leq n$ | A |
| $18 \sim 21$ | ^ | ^ | B |
| $22 \sim 25$ | ^ | ^ | 无 |


特殊性质 A: 对于所有 $1 \leq i \leq n$，均有 $s_i = 1$。

特殊性质 B: 在 $s_1, s_2, \dots, s_n$ 中最多只有 18 个取值为 1，即 $\sum_{i=1}^{n} s_i \leq 18$。

输入样例 复制 

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

输出样例 复制 

2204128

分类标签