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 翻译