/ ep / 题库 /

种花

种花

题目描述

现在有一行花田,共有n个可以种花的位置,我们有m种不同的花, 每种各一束
规定种花时两棵花不能种在相邻位置
求种花的方案总数(全部都要种下)
如果种花的位置不同或者至少一个位置种的花种类不同,就认为两个方案是不同的
由于答案可能很大,所以输出结果对q取模

输入

输入一行,共3个整数n,m,q

输出

输出一个整数,表示种花方案数,输出结果对q取模

输入样例

3 2 10007

输出样例

2

数据范围与限制

对于50%的数据,有\(n\leq3000,m\leq1500\)
对于80%的数据,保证q为质数
对于100%的数据有\(n\leq200000,1\leq m \leq100000,1\leq q\leq10^9,m\leq\lceil \frac{n}{2} \rceil\)
时间限制1s,空间限制256m

信息

ID
1006
难度
5
分类
组合数学 点击显示
标签
(无)
递交数
11
已通过
2
通过率
18%
上传者

相关

在下列训练计划中:

新生入门训练计划