D - Convex Sequence

Contest Duration: 2020-11-14(Sat) 12:00 - 2020-11-14(Sat) 15:20 (local time) (200 minutes) Back to Home

D - Convex Sequence Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $1000$ 点

問題文

整数 $N$ と $M$ が与えられます．長さ $N$ の非負整数列 $(A_1,A_2,\ldots,A_N)$ であって，次の条件を満たすものの個数を $\bmod (10^9+7)$ で求めてください．

$A_1+A_2+\ldots +A_N = M$
すべての $i$ ( $2 \leq i \leq N-1$ ) について， $2 A_i \leq A_{i-1} + A_{i+1}$

制約

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
入力はすべて整数である．

入力

入力は以下の形式で標準入力から与えられる．

 $N$   $M$

出力

条件を満たす数列の個数を $\bmod (10^9+7)$ で出力せよ．

入力例 1Copy

Copy

3 3

出力例 1Copy

Copy

以下の $7$ 個の数列が条件を満たします．

$0,0,3$
$0,1,2$
$1,0,2$
$1,1,1$
$2,0,1$
$2,1,0$
$3,0,0$

入力例 2Copy

Copy

10 100

出力例 2Copy

Copy

10804516

入力例 3Copy

Copy

10000 100000

出力例 3Copy

Copy

694681734

Score : $1000$ points

Problem Statement

Given are integers $N$ and $M$ . Find the number, modulo $(10^9+7)$ , of length- $N$ sequences $(A_1,A_2,\ldots,A_N)$ that consist of non-negative integers and satisfy the following conditions:

$A_1+A_2+\ldots +A_N = M$ ;
For every $i$ ( $2 \leq i \leq N-1$ ), $2 A_i \leq A_{i-1} + A_{i+1}$ .

Constraints

$1 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

 $N$   $M$

Output

Print the number, modulo $(10^9+7)$ , of sequences that satisfy the conditions.

Sample Input 1Copy

Copy

3 3

Sample Output 1Copy

Copy

The following seven sequences satisfy the conditions.

$0,0,3$
$0,1,2$
$1,0,2$
$1,1,1$
$2,0,1$
$2,1,0$
$3,0,0$

Sample Input 2Copy

Copy

10 100

Sample Output 2Copy

Copy

10804516

Sample Input 3Copy

Copy

10000 100000

Sample Output 3Copy

Copy

694681734