問題一覧 > 通常問題

No.1474 Kasama J

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 72
作問者 : gorugo30 / テスター : 37zigen nok0
お気に入りにしたユーザー ProblemId : 5960 / 自分の提出
問題文最終更新日: 2021-04-04 08:22:34
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 290 (順位表) の他の問題:

Problem Statement

Kazoe-san was planning to distribute a total of $M_P$ "P"s among $N$ people.
However, feeling that just $M_P$ "P"s were not satisfying enough, Kazoe-san prepared $M_q$ "q"s and decided to distribute them at the same time.
Kazoe-san's goal is that nobody notices that "q"s are mixed in.

The $N$ people are called person $1$, person $2$, $\ldots$, person $N$.
Person $i$ notices that "q"s are mixed in in the following cases:

  • More than $S_i$ "q"s are given to person $i$.
  • The total number of "P"s and "q"s given to person $i$ is less than $L$, and $1$ or more "q"s are given to that person.
Here, $S_i < L$, so giving $L$ or more "q"s to person $i$ will always be noticed.

How many ways are there to distribute the $M_P$ "P"s and between $0$ and $M_q$ "q"s, inclusive, that achieve Kazoe-san's goal?

Two distributions are considered different if there exists a person for whom the number of "P"s or the number of "q"s given differs.
Print the answer modulo $10^9 + 7$. A distribution may leave some people with $0$ "P"s and "q"s both.

Input

$N\ M_P\ M_q\ L$
$S_1\ S_2\ \ldots\ S_N$

  • $1\leq N\leq 40$
  • $1\leq M_P\leq 20000$
  • $0\leq M_q\leq 20000$
  • $1\leq L\leq 10000$
  • $0\leq S_i< L$
  • All inputs are integers.

Output

Print a newline at the end.

Sample

Sample 1
Input
2 3 0 2
1 1
Output
4

There are $4$ ways to distribute $3$ "P"s among $2$ people.

Sample 2
Input
2 2 1 2
1 1
Output
7

In this example, the values of $S_i$ are at least $M_q$, so nobody will notice because of being given more "q"s than $S_i$.
However, if a person is given no "P"s and just $1$ "q", the total number of "P"s and "q"s given is $1$, which is less than $L$, so that person will notice.

Specifically, letting $X_i$ be the number of "P"s and $Y_i$ be the number of "q"s given to person $i$,
there are the following 7 ways: $((X_1, Y_1), (X_2, Y_2)) = ((0, 0), (2, 0))$, $((2, 0), (0, 0))$, $((1, 0), (1, 0))$, $((0, 0), (2, 1))$, $((2, 1), (0, 0))$, $((1, 1), (1, 0))$, and $((1, 0), (1, 1))$.

Sample 3
Input
10 1000 500 300
3 141 59 26 53 58 9 79 3 238
Output
595400382

Sample 4
Input
40 20000 20000 10000
2157 1034 6876 6167 5896 500 3354 8114 1607 3534 1655 9796 7967 2942 2745 2401 3813 4770 6036 4858 2479 3793 2714 2029 9078 6633 9111 1285 6800 4795 2241 6173 6797 184 6243 3366 470 6136 2187 8257
Output
590015951

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。