4734: 鸡(广东省重点中学信息学邀请赛提高组)
内存限制：512 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
广东省重点中学信息学邀请赛(GDKOI 2024 day1提高组第一试)
对于一个非负整数序列a，定义它对应的独立集序列f(a)：
•假设将ai改为0，此时选出若干个两两不相邻的数使得它们的和最大，则f(a)i表示和的最大值。
现在给定n,m，求有多少个长度为b的非负整数序列b满足以下条件：
•存在至少一个长度为n，值域为[0,m]的非负整数序列a使得f(a)=b。
答案对给定的质数MOD取模。
对于一个非负整数序列a，定义它对应的独立集序列f(a)：
•假设将ai改为0，此时选出若干个两两不相邻的数使得它们的和最大，则f(a)i表示和的最大值。
现在给定n,m，求有多少个长度为b的非负整数序列b满足以下条件：
•存在至少一个长度为n，值域为[0,m]的非负整数序列a使得f(a)=b。
答案对给定的质数MOD取模。
输入
共一行，三个数，表示n,m,MOD。
输出
共一行，一个数，表示答案。
样例输入 复制
3 1 1000000007
4 2 1000000007
20 24 1000000007
123 234 1000000009
1234 2345 1004535809样例输出 复制
6
47
901565358
141754844
576196526提示
数据范围：
本题使用子任务捆绑测试。
对于100%的数据，1≤n,m≤3×103，n≥2，109<MOD<1.01×109，MOD为质数。
Subtask1(10%):n,m≤5。
Subtask2(15%):n≤300，m=1。
Subtask3(25%):n≤300，m≤5。
Subtask4(20%):n,m≤50。
Subtask5(15%):n,m≤300。
Subtask6(15%):无特殊限制。
本题使用子任务捆绑测试。
对于100%的数据，1≤n,m≤3×103，n≥2，109<MOD<1.01×109，MOD为质数。
Subtask1(10%):n,m≤5。
Subtask2(15%):n≤300，m=1。
Subtask3(25%):n≤300，m≤5。
Subtask4(20%):n,m≤50。
Subtask5(15%):n,m≤300。
Subtask6(15%):无特殊限制。