转向数组
给定整数 n,m,mod。
对于一个 1∼n 的排列 p=(p1,p2,…,pn),定义长度为 n−1 的数组 b(p)。对于每个 1≤i<n:
- 在所有满足 i<j<n 且 [pi+1>pi]=[pj+1>pi] 的下标 j 中,取最小的一个,令 bi(p)=j;
- 如果不存在这样的 j,则令 bi(p)=n。
其中,[S] 表示:若命题 S 成立,其值为 1;否则为 0。
称一个长度为 n−1 的整数数组 a 是好的,当且仅当同时满足:
- 对于每个 1≤i<n,都有 i+1≤ai≤min(n,i+m);
- 存在至少一个 1∼n 的排列 p,使得 a=b(p)。
求不同的好数组的数量,对 mod 取模。只要两个数组在至少一个位置上的值不同,就认为它们不同。同一个数组即使对应多个排列,也只计数一次。
输入格式
一行三个整数 n,m,mod。每个测试点只有一组输入数据。
输出格式
输出一行一个整数,表示不同的好数组的数量对 mod 取模的结果。
样例 1
4 3 100000000
6
六个好数组分别为 (2,3,4)、(2,4,4)、(3,3,4)、(3,4,4)、(4,3,4)、(4,4,4)。
样例 2
5 3 1000000007
17
例如,排列 p=(3,1,2,5,4) 对应好数组 a=(3,5,5,5)。对于 i=1,p2<p1、p3<p1,而 p4>p1,所以满足条件的最小下标为 j=3,即 a1=3。
样例 3
20 7 1000000007
575731297
数据范围
对于所有测试点,保证:
$$1\le m<n\le1000,\qquad m\le250,\qquad 10^8\le\mathrm{mod}\le10^9+7.$$
不保证 mod 是质数。
| 子任务 |
分值 |
限制 |
| 1 |
4 |
n≤9 |
| 2 |
6 |
n≤12 |
| 3 |
2 |
m=1 |
| 4 |
5 |
m=2 |
| 5 |
7 |
m≤8 |
| 6 |
5 |
m≤32 |
| 7 |
4 |
m≤100 |
| 8 |
m≤160 |
| 9 |
5 |
n≤25 |
| 10 |
n≤60 |
| 11 |
8 |
m=n−1 |
| 12 |
6 |
m=n−2 |
| 13 |
4 |
n−m≤8 |
| 14 |
5 |
n≤300 |
| 15 |
10 |
n≤600 |
| 16 |
20 |
无额外限制 |
各子任务独立计分。每个子任务采用捆绑测试,只有通过该子任务的全部测试点才能获得其分数。