鹿島建設プログラミングコンテスト2020 (AtCoder Regular Contest 110)
翻译中…
Problem Statement
翻译中…
We have a sequence $A$ of $N$ non-negative integers.
翻译中…
Compute the sum of $\prod _{i = 1} ^N \dbinom{B_i}{A_i}$ over all sequences $B$ of $N$ non-negative integers whose sum is at most $M$, and print it modulo ($10^9 + 7$).
翻译中…
Here, $\dbinom{B_i}{A_i}$, the binomial coefficient, denotes the number of ways to choose $A_i$ objects from $B_i$ objects, and is $0$ when $B_i < A_i$.
翻译中…
Constraints
翻译中…
- All values in input are integers.
$1 \leq N \leq 2000$$1 \leq M \leq 10^9$$0 \leq A_i \leq 2000$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N M
A_1 A_2 \ldots A_N翻译中…
Output
翻译中…
Print the sum of $\prod _{i = 1} ^N \dbinom{B_i}{A_i}$, modulo $(10^9 + 7)$.
翻译中…
样例
Input #1
3 5
1 2 1
Output #1
8
There are four sequences $B$ such that $\prod _{i = 1} ^N \dbinom{B_i}{A_i}$ is at least $1$:
- $B = \{1, 2, 1\}$, where $\prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1$;
- $B = \{2, 2, 1\}$, where $\prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2$;
- $B = \{1, 3, 1\}$, where $\prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3$;
- $B = \{1, 2, 2\}$, where $\prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2$.
The sum of these is $1 + 2 + 3 + 2 = 8$.
Input #2
10 998244353
31 41 59 26 53 58 97 93 23 84
Output #2
642612171
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。