#P18808. [2027年国家集训队互测]转向数组

[2027年国家集训队互测]转向数组

转向数组

给定整数 n,m,modn,m,\mathrm{mod}。

对于一个 1∼n1\sim n 的排列 p=(p1,p2,…,pn)p=(p_1,p_2,\ldots,p_n),定义长度为 n−1n-1 的数组 b(p)b(p)。对于每个 1≤i<n1\le i<n:

  • 在所有满足 i<j<ni<j<n 且 [pi+1>pi]≠[pj+1>pi][p_{i+1}>p_i]\ne[p_{j+1}>p_i] 的下标 jj 中,取最小的一个,令 bi(p)=jb_i(p)=j;
  • 如果不存在这样的 jj,则令 bi(p)=nb_i(p)=n。

其中,[S][S] 表示:若命题 SS 成立,其值为 11;否则为 00。

称一个长度为 n−1n-1 的整数数组 aa 是好的,当且仅当同时满足:

  1. 对于每个 1≤i<n1\le i<n,都有 i+1≤ai≤min⁡(n,i+m)i+1\le a_i\le\min(n,i+m);
  2. 存在至少一个 1∼n1\sim n 的排列 pp,使得 a=b(p)a=b(p)。

求不同的好数组的数量,对 mod\mathrm{mod} 取模。只要两个数组在至少一个位置上的值不同,就认为它们不同。同一个数组即使对应多个排列,也只计数一次。

输入格式

一行三个整数 n,m,modn,m,\mathrm{mod}。每个测试点只有一组输入数据。

输出格式

输出一行一个整数,表示不同的好数组的数量对 mod\mathrm{mod} 取模的结果。

样例 1

4 3 100000000
6

六个好数组分别为 (2,3,4)(2,3,4)、(2,4,4)(2,4,4)、(3,3,4)(3,3,4)、(3,4,4)(3,4,4)、(4,3,4)(4,3,4)、(4,4,4)(4,4,4)。

样例 2

5 3 1000000007
17

例如,排列 p=(3,1,2,5,4)p=(3,1,2,5,4) 对应好数组 a=(3,5,5,5)a=(3,5,5,5)。对于 i=1i=1,p2<p1p_2<p_1、p3<p1p_3<p_1,而 p4>p1p_4>p_1,所以满足条件的最小下标为 j=3j=3,即 a1=3a_1=3。

样例 3

20 7 1000000007
575731297

数据范围

对于所有测试点,保证:

$$1\le m<n\le1000,\qquad m\le250,\qquad 10^8\le\mathrm{mod}\le10^9+7.$$

不保证 mod\mathrm{mod} 是质数。

子任务 分值 限制
1 4 n≤9n\le9
2 6 n≤12n\le12
3 2 m=1m=1
4 5 m=2m=2
5 7 m≤8m\le8
6 5 m≤32m\le32
7 4 m≤100m\le100
8 m≤160m\le160
9 5 n≤25n\le25
10 n≤60n\le60
11 8 m=n−1m=n-1
12 6 m=n−2m=n-2
13 4 n−m≤8n-m\le8
14 5 n≤300n\le300
15 10 n≤600n\le600
16 20 无额外限制

各子任务独立计分。每个子任务采用捆绑测试,只有通过该子任务的全部测试点才能获得其分数。