AtCoder Regular Contest 215
递增。AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)For a sequence $A = (A_1, A_2, \ldots, A_{N+1})$ of length $N+1$, consider obtaining a sequence $S = (S_1, S_2, \ldots, S_N)$ of length $N$ in the following way.
对于一个长度为 $N+1$ 的序列 $A = (A_1, A_2, \ldots, A_{N+1})$，按如下方式构造长度为 $N$ 的序列 $S = (S_1, S_2, \ldots, S_N)$：AI (CI翻译)
- For each
$i$($1 \le i \le N$), let$S_i = A_i + A_{i+1}$.
- 对每个
$i$（$1 \le i \le N$），令$S_i = A_i + A_{i+1}$。
Find the number, modulo $10^9 + 7$, of sequences $S$ of length $N$ satisfying all of the following conditions.
求满足以下所有条件的长度为 $N$ 的序列 $S$ 的数量，答案对 $10^9 + 7$ 取模。AI (CI翻译)
$S$is non-decreasing.- There exists a sequence
$A$of length$N+1$consisting of integers between$0$and$M$, inclusive, such that$S$can be obtained from$A$in the way described above.
$S$是非递减序列。- 存在一个长度为
$N+1$的整数序列$A$，其中每个元素都在$0$到$M$（含）之间，并且可以按上述方式由$A$构造出$S$。
Constraints
约束条件
AI (CI翻译)$1 \le N, M \le 10^7$- All input values are integers.
$1 \le N, M \le 10^7$- 输入的所有数值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N MN MOutput
输出格式
AI (CI翻译)Output the answer on a single line.
在一行中输出答案。AI (CI翻译)
样例
Input #1
2 1
Output #1
5
The possible sequences $A$ are the following eight:
- $A = (0,0,0)$, for which $S = (0,0)$
- $A = (0,0,1)$, for which $S = (0,1)$
- $A = (0,1,0)$, for which $S = (1,1)$
- $A = (0,1,1)$, for which $S = (1,2)$
- $A = (1,0,0)$, for which $S = (1,0)$
- $A = (1,0,1)$, for which $S = (1,1)$
- $A = (1,1,0)$, for which $S = (2,1)$
- $A = (1,1,1)$, for which $S = (2,2)$
Among these, we have five distinct non-decreasing $S$: $(0,0),(0,1),(1,1),(1,2),(2,2)$.
Input #2
869121 10000000
Output #2
767557322
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。