A6281. Welcome24ever 和方块
编程题
提高+/省选-
知识点
题目描述
Welcome24ever 喜欢折叠和粘贴，今天他又开始玩方块了。
他有 $n$ 个立方体，从左到右排成一行，编号为 $1 \sim n$，每个立方体上写着一个正整数 $a_i$。另外，他还有 $k$ 张带有感叹号
对于某一个立方体，如果 Welcome24ever 在它上面贴上一张感叹号贴纸，那么这个立方体上的数字会立刻变成**这个数的阶乘**。例如：
- 如果某个立方体上写着 $5$，贴上感叹号后，它就会变成 $5! = 120$。
现在，Welcome24ever 想从这 $n$ 个立方体中选出若干个（也可以一个都不选），然后在被选中的立方体中，**最多选 $k$ 个**贴上感叹号。这样，每个被选中的立方体上最终会显示一个数（可能是原数，也可能是阶乘），所有被选中立方体上的最终数字之和要**恰好等于**给定的 $S$。
要求：
- 每个立方体**最多只能贴一张**感叹号贴纸；
- 如果两种方案中：
- 被选中的立方体集合相同，且
- 贴上感叹号的立方体集合也相同，
那么这两种方案视为**同一种方案**。
请你计算：一共有多少种不同的方案，使得所有被选中立方体上的最终数字之和恰好为 $S$。
他有 $n$ 个立方体，从左到右排成一行，编号为 $1 \sim n$，每个立方体上写着一个正整数 $a_i$。另外，他还有 $k$ 张带有感叹号
'!' 的贴纸（可以把它当作“阶乘”操作），并且我们知道 $k \le n$。对于某一个立方体，如果 Welcome24ever 在它上面贴上一张感叹号贴纸，那么这个立方体上的数字会立刻变成**这个数的阶乘**。例如：
- 如果某个立方体上写着 $5$，贴上感叹号后，它就会变成 $5! = 120$。
现在，Welcome24ever 想从这 $n$ 个立方体中选出若干个（也可以一个都不选），然后在被选中的立方体中，**最多选 $k$ 个**贴上感叹号。这样，每个被选中的立方体上最终会显示一个数（可能是原数，也可能是阶乘），所有被选中立方体上的最终数字之和要**恰好等于**给定的 $S$。
要求：
- 每个立方体**最多只能贴一张**感叹号贴纸；
- 如果两种方案中：
- 被选中的立方体集合相同，且
- 贴上感叹号的立方体集合也相同，
那么这两种方案视为**同一种方案**。
请你计算：一共有多少种不同的方案，使得所有被选中立方体上的最终数字之和恰好为 $S$。
输入格式
第一行包含三个整数 $n, k, S$：
- $1 \le n \le 25$ —— 立方体的数量；
- $0 \le k \le n$ —— 感叹号贴纸的数量（最多可使用的阶乘操作次数）；
- $1 \le S \le 10^{16}$ —— 目标总和。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$：
- $1 \le a_i \le 10^9$。
立方体按输入顺序从左到右视为 $1 \sim n$。
不同立方体上的数字可以相同。
- $1 \le n \le 25$ —— 立方体的数量；
- $0 \le k \le n$ —— 感叹号贴纸的数量（最多可使用的阶乘操作次数）；
- $1 \le S \le 10^{16}$ —— 目标总和。
第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$：
- $1 \le a_i \le 10^9$。
立方体按输入顺序从左到右视为 $1 \sim n$。
不同立方体上的数字可以相同。
输出格式
输出一个整数，表示一共有多少种不同的方案，使得选出的立方体在进行“原数 / 阶乘”的最终处理后，它们的和恰好等于 $S$。
输入输出样例
输入 #1
2 2 30 4 3
输出 #1
1
输入 #2
2 2 7 4 3
输出 #2
1
输入 #3
3 1 1 1 1 1
输出 #3
6
说明/提示
### 样例解释 #1
唯一的方案是：
- 选中两个立方体；
- 在两个立方体上都贴上感叹号：
$$ 4! + 3! = 24 + 6 = 30. $$
### 样例解释 #2
唯一的方案是：
- 选中两个立方体；
- 都**不**贴感叹号：
$$ 4 + 3 = 7. $$
### 样例解释 #3
共有三块写着
- 可以选择其中任意一个（3 种选法），
- 对于每个被选中的立方体，又可以选择“贴”或“不贴”感叹号（但不论是否贴，值都是 1），
因此共有 $3 \times 2 = 6$ 种不同的方案。
唯一的方案是：
- 选中两个立方体；
- 在两个立方体上都贴上感叹号：
$$ 4! + 3! = 24 + 6 = 30. $$
### 样例解释 #2
唯一的方案是：
- 选中两个立方体；
- 都**不**贴感叹号：
$$ 4 + 3 = 7. $$
### 样例解释 #3
共有三块写着
1 的立方体：- 可以选择其中任意一个（3 种选法），
- 对于每个被选中的立方体，又可以选择“贴”或“不贴”感叹号（但不论是否贴，值都是 1），
因此共有 $3 \times 2 = 6$ 种不同的方案。