分数: 1600 点
问题陈述
优化问题给你一个长度-N 非负整数序列 A=(A_1,A_2,\dots,A_N)。另外,还有一个长度——N+1 非负整数序列 X=(0,0,\dots,0).
您现在将为 i=1,2,\dots,N:
- 选择一个整数 v 满意 0 \le v \le A_i,并添加 v 和 A_i-v to X_i 和 X_{i+1}。
找出最大值的最小可能值 X 在操作结束时。
给你正整数 N, M,和一个素数 P。求总和,取模 P的答案 优化问题 对于所有序列 A=(A_1,A_2,\dots,A_N) 具有长度的非负整数 N 和总和 M.
约束
- 1 \le N \le 100
- 1 \le M \le 10^{18}
- 9 \times 10^8 \le P \le 10^9
- P 是质数。
输入
输入由标准输入按以下格式给出:
N M P
输出
输出总和,模数 P的答案 优化问题.
示例输入 1
3 3 998244353
示例输出 1
13
例如,我们解决 优化问题 为 A=(1,0,2)。以下是可能的操作顺序:
- 对于 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 和三个带有答案的序列 2,所以总和是 13.
示例输入 2
10 135 998244353
示例输出 2
679877945
示例输入 3
100 1000000000000000000 924844033
示例输出 3
789282612