A6208. 和風いろはちゃん
编程题
普及+/提高
知识点
题目描述
日本引以为傲的美丽韵律中,有一种叫做五七五。いろは酱决定在数列中寻找五七五。但这太简单了,于是她决定去寻找 XYZ。
给定一个长度为 $N$ 的数列 $a_0, a_1, \ldots, a_{N-1}$,其中每个元素的取值范围为 $1$ 到 $10$。这样的数列共有 $10^N$ 种可能。请问,其中包含 XYZ 的数列有多少种?
这里,包含 XYZ 被定义如下:
- 存在 $0 \leq x < y < z < w \leq N$,使得
- $a_x + a_{x+1} + \cdots + a_{y-1} = X$
- $a_y + a_{y+1} + \cdots + a_{z-1} = Y$
- $a_z + a_{z+1} + \cdots + a_{w-1} = Z$
请输出包含 XYZ 的数列个数。由于答案可能非常大,请输出对 $10^9+7$ 取模后的结果。
给定一个长度为 $N$ 的数列 $a_0, a_1, \ldots, a_{N-1}$,其中每个元素的取值范围为 $1$ 到 $10$。这样的数列共有 $10^N$ 种可能。请问,其中包含 XYZ 的数列有多少种?
这里,包含 XYZ 被定义如下:
- 存在 $0 \leq x < y < z < w \leq N$,使得
- $a_x + a_{x+1} + \cdots + a_{y-1} = X$
- $a_y + a_{y+1} + \cdots + a_{z-1} = Y$
- $a_z + a_{z+1} + \cdots + a_{w-1} = Z$
请输出包含 XYZ 的数列个数。由于答案可能非常大,请输出对 $10^9+7$ 取模后的结果。
输入格式
输入从标准输入读取,格式如下:
> $N$ $X$ $Y$ $Z$
> $N$ $X$ $Y$ $Z$
输出格式
输出包含 XYZ 的数列个数,对 $10^9+7$ 取模后的结果。
输入输出样例
输入 #1
3 5 7 5
输出 #1
1
输入 #2
4 5 7 5
输出 #2
34
输入 #3
37 4 2 3
输出 #3
863912418
输入 #4
40 5 7 5
输出 #4
562805100
说明/提示
### 限制条件
- $3 \leq N \leq 40$
- $1 \leq X \leq 5$
- $1 \leq Y \leq 7$
- $1 \leq Z \leq 5$
### 样例解释 1
只有数列 $\{5,7,5\}$ 满足条件。
- $3 \leq N \leq 40$
- $1 \leq X \leq 5$
- $1 \leq Y \leq 7$
- $1 \leq Z \leq 5$
### 样例解释 1
只有数列 $\{5,7,5\}$ 满足条件。