[GDKOI2024 提高组] 鸡

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

提高组 第一试

2024 年 1 月 6 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$：

• 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。

现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件：

• 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。

答案对给定的质数 $\textit{MOD}$ 取模。

输入格式

共一行，三个数，表示 $n, m, \textit{MOD}$。

输出格式

共一行，一个数，表示答案。

样例 #1

样例输入 #1

3 1 1000000007

样例输出 #1

6

样例 #2

样例输入 #2

4 2 1000000007

样例输出 #2

47

样例 #3

样例输入 #3

20 24 1000000007

样例输出 #3

901565358

样例 #4

样例输入 #4

123 234 1000000009

样例输出 #4

141754844

样例 #5

样例输入 #5

1234 2345 1004535809

样例输出 #5

576196526

提示

本题使用子任务捆绑测试。

对于 $100\%$ 的数据，$1 \leq n, m \leq 3 \times 10^3$，$n \geq 2$，$10^9 < \textit{MOD} < 1.01 \times 10^9$，$\textit{MOD}$ 为质数。

• Subtask 1（10%）：$n, m \leq 5$。
• Subtask 2（15%）：$n \leq 300$，$m = 1$。
• Subtask 3（25%）：$n \leq 300$，$m ≤ 5$。
• Subtask 4（20%）：$n, m \leq 50$。
• Subtask 5（15%）：$n, m \leq 300$。
• Subtask 6（15%）：无特殊限制。