#P15023. [2026省选联测]Game1

    ID: 14239 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400动态规划计数DP前缀和组合数学构造

[2026省选联测]Game1

题目描述

小 ς\varsigma 发明了一款游戏,规则如下:

  • 一行 nn 个格子,每格要么为空,要么有一个方块。
  • 初始时:某一格生成一个权值 11 的方块,其出现时间定义为 11。
  • 小 Y 可以进行若干次操作直到游戏失败或胜利(失败和胜利定义见下),第 ii 次操作(向左或右滑动):
    1. 方块全部向一侧紧贴。
    2. 若相邻两个方块权值相等,则合并成一个权值为这两个方块的权值加 11 的方块(可以证明不会出现连续三个相等的情况),合并生成的方块出现时间为 2i2i,随后所有方块继续向左(或右)堆叠,直到不存在能合并的情况为止。
    3. 在另一端生成一个新的 11,出现时间为 2i+12i+1。若格子已满,则无法生成新方块,游戏失败。
  • 若某次出现 xx,则立即胜利。

定义两个失败状态 本质相同 当且仅当:

  1. 每个格子的权值相同;
  2. 所有方块出现时间的相对大小关系相同。

求共有多少种 本质不同的失败状态,答案对 pp 取模(不保证 pp 为质数)。

输入格式

从文件 game1.in 中输入数据。

本题有多组测试数据。

第一行,两个正整数 T,pT, p,分别表示数据组数和模数。对于每组数据:仅一行,两个整数 n,xn, x。

输出格式

输出到文件 game1.out 中。

对于每组数据:仅一行一个正整数,表示本质不同的失败状态数,答案对 pp 取模。

输入输出样例

输入1

5 71
3 4
4 3
4 4
4 5
5 6

输出1

8
0
12
34
20

【样例1解释 】

对于第一组数据,n=3n = 3,x=4x = 4:

  • 仅从网格状态上看,共有 66 种失败的可能性:$[3,2,1], [1,2,3], [1,3,2], [2,3,1], [1,3,1],[1,2,1]$。
    • 但考虑 [1,3,1][1,3,1] 和 [1,2,1][1,2,1],其可以对应两种本质不同的失败状态,以 [1,3,1][1,3,1] 为例:
      • 中间的 33 先被生成,随后左边的 11 生成,随后右边的 11 生成;
      • 中间的 33 先被生成,随后右边的 11 生成,随后左边的 11 生成。
  • 所以,答案为 1+1+1+1+2+2=81 + 1 + 1 + 1 + 2 + 2 = 8,在模 7171 意义下为 88。

对于第二组数据,n=4n = 4,x=3x = 3:

  • 不存在任何失败状态,答案为 00。

对于第三组数据,n=4n = 4,x=4x = 4:

  • 仅从网格状态上看,共有 44 种失败的可能性:[1,3,2,1],[1,2,3,1],[2,3,2,1],[1,2,3,2][1,3,2,1], [1,2,3,1], [2,3,2,1],[1,2,3,2]。其中,[1,3,2,1][1,3,2,1] 和 [1,2,3,1][1,2,3,1] 分别对应 44 种本质不同的失败情况,[2,3,2,1][2,3,2,1] 和 [1,2,3,1][1,2,3,1] 分别对应 22 种本质不同的失败情况。所以,答案为 4+4+2+2=124 + 4 + 2 + 2 = 12,在模 7171 意义下为 1212。

对于第四组数据,n=4n = 4,x=5x = 5:

  • 答案为 3434,在模 7171 意义下为 3434。

对于第五组数据,n=5n = 5,x=6x = 6:

  • 答案为 162162,在模 7171 意义下为 2020。

输入2

10 114514
5 10
1 1
9 10
1 5
4 20
3 17
3 16
11 13
51 76
241 261

输出2

162
0
21708
1
34
8
8
69166
70264
3040

数据范围

本题共 2525 个测试点,每个 44 分。

测试点编号 T≤T \le n,x≤n,x \le 特殊性质
1∼21\sim2 1010 44 无
3∼53\sim5 1010
6∼106\sim10 2222
11∼1311\sim13 11 8080
14∼1714\sim17 10001000
18∼2018\sim20 11 300300
2121 10510^5 p=2p = 2
22∼2522\sim25 无

对于全部数据,保证:1≤T≤1051\le T\le 10^5,1≤n,x≤3001\le n,x\le 300,2≤p≤1092\le p\le10^9。