AT_agc075_e.[AGC075E] Many Optimization Problems

优化问题
给定一个长度为 $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$ 加到 $X_i$ 上，将 $A_i-v$ 加到 $X_{i+1}$ 上。

求所有操作完成后，$X$ 中所有元素的最大值的最小可能值。

你将被给定正整数 $N$、$M$ 和一个质数 $P$。求所有长度为 $N$、且所有元素为非负整数、且元素和为 $M$ 的序列 $A=(A_1,A_2,\dots,A_N)$ 下，优化问题的答案之和对 $P$ 取模的结果。

输入通过标准输入给出，格式如下：

$N$ $M$ $P$

输出所有满足条件的序列 $A$ 的优化问题的答案之和对 $P$ 取模的结果。

样例解释 1

以 $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$。

对于该情况还有 6 个序列的答案为 1，3 个序列的答案为 2，因此总和为 13。

数据范围

• $1 \le N \le 100$
• $1 \le M \le 10^{18}$
• $9\times 10^8 \le P \le 10^9$
• $P$ 为质数。

由 ChatGPT 5 翻译