← 返回题目列表

AtCoder · agc075_e

E. 许多优化问题

中文机器翻译题面 查看原题

分数: 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