编程题：教科书般的亵渎
九条可怜最近在玩一款卡牌游戏。在每一局游戏中，可怜都要使用抽到的卡牌来消灭一些敌人。每一名敌人都有一个初始血量，而当血量降低到 $$0$$ 及以下的时候，这名敌人就会立即被消灭并从场上消失。
现在，可怜面前有 $$n$$ 个敌人，其中第 $$i$$ 名敌人的血量是 $$a_i$$，而可怜手上只有如下两张手牌：
1. 如果场上还有敌人，等概率随机选中一个敌人并对它造成一点伤害（即血量减 $$1$$），重复 $$K$$ 次。
2. 对所有敌人造成一点伤害，重复该效果直到没有新的敌人被消灭。
下面是这两张手牌效果的一些示例：
1. 假设存在两名敌人，他们的血量分别是 $$1, 2$$ 且 $$K = 2$$。那么在可怜打出第一张手牌后，可能会发生如下情况：
- 第一轮中，两名敌人各有 $$0.5$$ 的概率被选中。假设第一名敌人被选中，那么它会被造成一点伤害。这时它的血量变成了 $$0$$，因此它被消灭并消失了。
- 第二轮中，因为场上只剩下了第二名敌人，所以它一定会被选中并被造成一点伤害。这时它剩下的血量为 $$1$$。
2. 同样假设存在两名敌人且血量分别为 $$1, 2$$。那么在可怜打出第二张手牌后，会发生如下情况：
- 第一轮中，所有敌人被造成了一点伤害。这时第一名敌人被消灭了，因此卡牌效果会被重复一遍。
- 第二轮中，所有敌人（此时只剩下第二名敌人了）被造成了一点伤害。这时第二名敌人也被消灭了，因此卡牌效果会被再重复一遍。
- 第三轮中，所有敌人（此时没有敌人剩下了）被造成了一点伤害。因为没有新的敌人被消灭了，所以卡牌效果结束。
3. 如果面对的是四名血量分别为 $$1,2,2,4$$ 的敌人，那么在可怜打出第二张手牌后，只有第四名敌人还会存活，且它的剩余血量为 $$1$$。
现在，可怜先打出了第一张手牌，再打出了第二张手牌。她发现，在第一张手牌效果结束后，没有任何一名敌人被消灭，但是在第二张手牌的效果结束后，所有敌人都被消灭了。
可怜想让你计算一下这种情况发生的概率是多少。
### 输入格式：
第一行输入两个整数 $$n, K(1 \le n, K \le 50)$$，分别表示敌人的数量以及第一张卡牌效果的发动次数。
第二行输入 $$n$$ 个由空格隔开的整数 $$a_i (1 \le a_i \le 50)$$，表示每个敌人的初始血量。
### 输出格式：
在一行中输出一个整数，表示发生概率对 $$998244353$$ 取模后的结果。
具体来说，如果概率的最简分数表示为 $$a/b (a \ge 0, b \ge 1, \gcd(a,b) = 1)$$，那么你需要输出
$$a \times b^{998244351} \mod 998244353$$。
### 输入样例 1：
in
3 2
2 3 3
### 输出样例 1：
out
665496236
### 样例解释 1：
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：$$[1, 3, 2]$$, $$[1, 2, 3]$$, $$[2, 1, 3]$$ 和 $$[2, 3, 1]$$。前两种发生的概率是 $$2/9$$，后两种发生的概率是 $$1/9$$。因此答案为 $$2/3$$，输出 $$2 \times 3^{998244351} \mod 998244353 = 665496236$$。
### 输入样例 2：
in
3 3
2 3 3
### 输出样例 2：
out
776412275
### 样例解释 2:
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：$$[1,2,2]$$、$$[2, 1, 2]$$ 和 $$ [2, 2, 1]$$。第一种发生的概率是 $$2/9$$，后两种发生的概率是 $$1/9$$。因此答案为 $$4/9$$，输出 $$4 \times 9^{998244351} \mod 998244353 = 776412275$$。
### 输入样例 3：
in
5 3
1 4 4 2 5
### 输出样例 3：
out
367353922
### 输入样例 4：
in
12 12
1 2 3 4 5 6 7 8 9 10 11 12
### 输出样例 4：
out
452061016
答案：若无答案欢迎评论
问题等价于给定一个数列，每次随机选择一个数减去 $1$，重复 $K$ 次。要求结束后存在一个整数 $m$ 满足 (1) 所有数都在 $[1,m]$ 范围内，且 (2) $[1,m]$ 内的每一个整数都至少出现了一次。
枚举 $m$ 的取值，考虑一个简单的状态压缩动态规划来计算合法的方案数。
令 $f[i][j][S]$ 表示考虑了所有初始值小于等于 $i$ 的数，还剩下 $j$ 次操作，且 $[1,m]$ 中还存在集合 $S$ 内的整数没有出现过的方案数。转移的时候对于每一个初始值等于 $i$ 的数字，枚举它被减了几次（假设是 $a$），将 $f[i][j][S] \times \binom{j}{a}$ 更新到 $f[i+1][j-i][S']$。（如果有多个等于 $i$ 的数字则需要几个中间状态，全枚举完后再更新到 $i+1$）。
考虑优化这个动态规划，不难发现 $S$ 中所有大于 $i$ 的位置信息都是没用的，因为小于等于 $i$ 的数在结束后不可能变得比 $i$ 大。所以状态中 $S$ 可以只记录小于等于 $i$ 的位置。
同时，如果我们要让 $f[i][j][S]$ 转移到一个合法的结果，那么必须要要让大于 $i$ 的数字去填补 $S$ 中的空缺，即至少需要 $\sum_{a \in S} (i + 1- a)$ 次操作。因此我们只需要保留 $\sum_{a \in S} (i + 1- a) \leq j$ 的状态。这样的集合 $S$ 数量等于和不超过 $K$ 且所有元素两两不同的集合数量。这样的集合数非常少，在 $K=50$ 的时候只有 $63166$ 个。
因此，在动态规划的时候，我们只需要考虑 $S$ 在这 $63166$ 个集合中的状态就可以了。配合上如下优化即可通过这题：
1. 不同的 $m$ 不需要重头开始计算，只需要单独计算最后的部分就行了。
2. 一个 $m $合法当且仅当 $K$ 次操作足以将所有比 $m$ 大的数变得比 $m$ 小，其余 $m$ 的取值都可以忽略。
现在，可怜面前有 $$n$$ 个敌人，其中第 $$i$$ 名敌人的血量是 $$a_i$$，而可怜手上只有如下两张手牌：
1. 如果场上还有敌人，等概率随机选中一个敌人并对它造成一点伤害（即血量减 $$1$$），重复 $$K$$ 次。
2. 对所有敌人造成一点伤害，重复该效果直到没有新的敌人被消灭。
下面是这两张手牌效果的一些示例：
1. 假设存在两名敌人，他们的血量分别是 $$1, 2$$ 且 $$K = 2$$。那么在可怜打出第一张手牌后，可能会发生如下情况：
- 第一轮中，两名敌人各有 $$0.5$$ 的概率被选中。假设第一名敌人被选中，那么它会被造成一点伤害。这时它的血量变成了 $$0$$，因此它被消灭并消失了。
- 第二轮中，因为场上只剩下了第二名敌人，所以它一定会被选中并被造成一点伤害。这时它剩下的血量为 $$1$$。
2. 同样假设存在两名敌人且血量分别为 $$1, 2$$。那么在可怜打出第二张手牌后，会发生如下情况：
- 第一轮中，所有敌人被造成了一点伤害。这时第一名敌人被消灭了，因此卡牌效果会被重复一遍。
- 第二轮中，所有敌人（此时只剩下第二名敌人了）被造成了一点伤害。这时第二名敌人也被消灭了，因此卡牌效果会被再重复一遍。
- 第三轮中，所有敌人（此时没有敌人剩下了）被造成了一点伤害。因为没有新的敌人被消灭了，所以卡牌效果结束。
3. 如果面对的是四名血量分别为 $$1,2,2,4$$ 的敌人，那么在可怜打出第二张手牌后，只有第四名敌人还会存活，且它的剩余血量为 $$1$$。
现在，可怜先打出了第一张手牌，再打出了第二张手牌。她发现，在第一张手牌效果结束后，没有任何一名敌人被消灭，但是在第二张手牌的效果结束后，所有敌人都被消灭了。
可怜想让你计算一下这种情况发生的概率是多少。
### 输入格式：
第一行输入两个整数 $$n, K(1 \le n, K \le 50)$$，分别表示敌人的数量以及第一张卡牌效果的发动次数。
第二行输入 $$n$$ 个由空格隔开的整数 $$a_i (1 \le a_i \le 50)$$，表示每个敌人的初始血量。
### 输出格式：
在一行中输出一个整数，表示发生概率对 $$998244353$$ 取模后的结果。
具体来说，如果概率的最简分数表示为 $$a/b (a \ge 0, b \ge 1, \gcd(a,b) = 1)$$，那么你需要输出
$$a \times b^{998244351} \mod 998244353$$。
### 输入样例 1：
in
3 2
2 3 3
### 输出样例 1：
out
665496236
### 样例解释 1：
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：$$[1, 3, 2]$$, $$[1, 2, 3]$$, $$[2, 1, 3]$$ 和 $$[2, 3, 1]$$。前两种发生的概率是 $$2/9$$，后两种发生的概率是 $$1/9$$。因此答案为 $$2/3$$，输出 $$2 \times 3^{998244351} \mod 998244353 = 665496236$$。
### 输入样例 2：
in
3 3
2 3 3
### 输出样例 2：
out
776412275
### 样例解释 2:
在第一张手牌的效果结束后，三名敌人的剩余血量只可能在如下几种中：$$[1,2,2]$$、$$[2, 1, 2]$$ 和 $$ [2, 2, 1]$$。第一种发生的概率是 $$2/9$$，后两种发生的概率是 $$1/9$$。因此答案为 $$4/9$$，输出 $$4 \times 9^{998244351} \mod 998244353 = 776412275$$。
### 输入样例 3：
in
5 3
1 4 4 2 5
### 输出样例 3：
out
367353922
### 输入样例 4：
in
12 12
1 2 3 4 5 6 7 8 9 10 11 12
### 输出样例 4：
out
452061016
答案：若无答案欢迎评论
问题等价于给定一个数列，每次随机选择一个数减去 $1$，重复 $K$ 次。要求结束后存在一个整数 $m$ 满足 (1) 所有数都在 $[1,m]$ 范围内，且 (2) $[1,m]$ 内的每一个整数都至少出现了一次。
枚举 $m$ 的取值，考虑一个简单的状态压缩动态规划来计算合法的方案数。
令 $f[i][j][S]$ 表示考虑了所有初始值小于等于 $i$ 的数，还剩下 $j$ 次操作，且 $[1,m]$ 中还存在集合 $S$ 内的整数没有出现过的方案数。转移的时候对于每一个初始值等于 $i$ 的数字，枚举它被减了几次（假设是 $a$），将 $f[i][j][S] \times \binom{j}{a}$ 更新到 $f[i+1][j-i][S']$。（如果有多个等于 $i$ 的数字则需要几个中间状态，全枚举完后再更新到 $i+1$）。
考虑优化这个动态规划，不难发现 $S$ 中所有大于 $i$ 的位置信息都是没用的，因为小于等于 $i$ 的数在结束后不可能变得比 $i$ 大。所以状态中 $S$ 可以只记录小于等于 $i$ 的位置。
同时，如果我们要让 $f[i][j][S]$ 转移到一个合法的结果，那么必须要要让大于 $i$ 的数字去填补 $S$ 中的空缺，即至少需要 $\sum_{a \in S} (i + 1- a)$ 次操作。因此我们只需要保留 $\sum_{a \in S} (i + 1- a) \leq j$ 的状态。这样的集合 $S$ 数量等于和不超过 $K$ 且所有元素两两不同的集合数量。这样的集合数非常少，在 $K=50$ 的时候只有 $63166$ 个。
因此，在动态规划的时候，我们只需要考虑 $S$ 在这 $63166$ 个集合中的状态就可以了。配合上如下优化即可通过这题：
1. 不同的 $m$ 不需要重头开始计算，只需要单独计算最后的部分就行了。
2. 一个 $m $合法当且仅当 $K$ 次操作足以将所有比 $m$ 大的数变得比 $m$ 小，其余 $m$ 的取值都可以忽略。
