/ 
実行時間制限: 5 sec / メモリ制限: 1024 MiB
配点 : 1600 点
問題文
Optimization Problem長さ N の非負整数列 A=(A_1,A_2,\dots,A_N) が与えられます。また、長さ N+1 の非負整数列 X=(0,0,\dots,0) があります。
あなたは今から i=1,2,\dots,N について以下の操作を行います。
- 0 \le v \le A_i を満たす整数 v を選び、X_i,X_{i+1} にそれぞれ v,A_i-v を加算する。
操作終了時の X の最大値としてあり得る値の最小値を求めてください。
正整数 N,M と素数 P が与えられます。長さ N かつ総和が M であるような非負整数列 A=(A_1,A_2,\dots,A_N) 全てに対する Optimization Problem の答えの総和を P で割った余りを求めてください。
制約
- 1 \le N \le 100
- 1 \le M \le 10^{18}
- 9 \times 10^8 \le P \le 10^9
- P は素数
入力
入力は以下の形式で標準入力から与えられる。
N M P
出力
Optimization Problem の答えの総和を P で割った余りを出力せよ。
入力例 1
3 3 998244353
出力例 1
13
例えば、A=(1,0,2) について Optimization Problem を解きます。例えば、操作列の一例として以下のようなものがあります。
- i = 1 では v = 1 とする。X=(1,0,0,0) となる。
- i = 2 では v = 0 とする。X=(1,0,0,0) となる。
- i = 3 では v = 1 とする。X=(1,0,1,1) となる。
X の最大値を 0 以下にすることは出来ないため、答えは 1 です。
これ以外に答えが 1 となる数列が 6 個、答えが 2 となる数列が 3 個あるためその総和は 13 です。
入力例 2
10 135 998244353
出力例 2
679877945
入力例 3
100 1000000000000000000 924844033
出力例 3
789282612
Score : 1600 points
Problem Statement
Optimization ProblemYou are given a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N). Also, there is a length-N+1 sequence of non-negative integers X=(0,0,\dots,0).
You will now perform the following operation for i=1,2,\dots,N:
- Choose an integer v satisfying 0 \le v \le A_i, and add v and A_i-v to X_i and X_{i+1}, respectively.
Find the minimum possible value of the maximum value of X at the end of the operations.
You are given positive integers N, M, and a prime number P. Find the sum, modulo P, of the answers to the Optimization Problem for all sequences A=(A_1,A_2,\dots,A_N) of non-negative integers with length N and sum M.
Constraints
- 1 \le N \le 100
- 1 \le M \le 10^{18}
- 9 \times 10^8 \le P \le 10^9
- P is prime.
Input
The input is given from Standard Input in the following format:
N M P
Output
Output the sum, modulo P, of the answers to the Optimization Problem.
Sample Input 1
3 3 998244353
Sample Output 1
13
For example, we solve the Optimization Problem for A=(1,0,2). Here is a possible sequence of operations:
- For i = 1, let v = 1. X becomes (1,0,0,0).
- For i = 2, let v = 0. X remains (1,0,0,0).
- For i = 3, let v = 1. X becomes (1,0,1,1).
Since the maximum value of X cannot be made 0 or less, the answer is 1.
There are six other sequences with answer 1 and three sequences with answer 2, so the sum is 13.
Sample Input 2
10 135 998244353
Sample Output 2
679877945
Sample Input 3
100 1000000000000000000 924844033
Sample Output 3
789282612