luogu#P11216. 【MX-J8-T4】2048

    ID: 35035 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>动态规划,dpO2优化区间 dp动态规划优化前缀和

【MX-J8-T4】2048

题目背景

原题链接:https://oier.team/problems/84


《2048》是一款非常好玩,火爆全球的小游戏。

题目描述

现在,小 Y 把《2048》稍做修改,得到如下的一维变种(其中部分规则可能与你对《2048》的印象相悖,请以下文为准):

  • 游戏在一行 nn 个格子组成的网格中进行。每个格子要么为空,要么包含一个带有正整数权值的方块。
  • 游戏开始时,会在一个任意的格子上生成一个权值为 22 的方块,其他格子为空。
  • 玩家通过向左(或右,下同)滑动进行操作。每次操作:
    1. 所有方块将全部靠左(或右)堆叠放置,彼此紧贴,不留空位。
    2. 如果堆叠完毕后,存在相邻的两个方块权值相等,设其权值均为 kk,则消除这两个方块,并在原先其中一个方块的位置生成一个权值为 2k2k 的方块(这称作一次合并)(可以证明,在该游戏过程中不会存在连续 3\bm 3 个相邻方块权值相等,因此不需要考虑合并顺序的问题),随后所有方块继续向左(或右)堆叠,直到不存在能合并的情况为止。
    3. 最后,在最右(或左)端,即滑动方向的相反方向,生成一个权值为 22 的新方块。

下图展示了一次向左滑动操作的示例。

  • 如下定义一个方块的出现时间
    • 设它被生成时,游戏进行的轮数(即玩家进行滑动操作的次数)为 ii(包括当前操作)。
    • 如果该方块是被合并生成的,令它的出现时间为 2i2 i
    • 否则该方块是新生成的,令它的出现时间为 2i+12 i + 1
    • 如果该方块是游戏最开始时生成的权值为 22 的方块,令它的出现时间为 11
    • 可以证明,按如上定义的出现时间满足:在游戏进行的任意时刻下,任意两个不同方块的出现时间均不同。
  • 游戏的目标是生成 2x2^x,因此在游戏的任何过程中,一旦出现了 2x2^x,游戏立刻结束,且游戏胜利。
  • 如果一次滑动操作的步骤 2 结束时,所有 nn 个格子全都包含方块(事实上,这次滑动操作是滑不动的,但仍然认为是一次滑动操作),则步骤 3 中无法正常生成新方块,不会进行步骤 3,且游戏失败。

小 Y 正在研究这个新 2048 游戏的所有失败状态的个数。具体地,在游戏失败时,两个失败状态 A 和 B 被认为本质相同,当且仅当以下条件同时成立:

  • 对每个 1in1 \leq i \leq n,A 中方块 ii 和 B 中方块 ii 的权值均相同;
  • 对每对 1i<jn1 \le i < j \le n,A 中的方块 ii 与方块 jj 的出现时间的大小关系,与 B 中的方块 ii 与方块 jj 的出现时间的大小关系相同。

小 Y 想要知道,总共有多少种本质不同的失败状态。答案对给定模数 pp 取模(pp 未必为素数)。

输入格式

本题有多组测试数据。

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

  • 仅一行,两个整数 n,xn, x

输出格式

对于每组数据:

  • 仅一行一个正整数,表示本质不同的失败状态数,答案对 pp 取模。
5 71
3 4
4 3
4 4
4 5
5 6

8
0
12
34
20

提示

【样例解释 #1】

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

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

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

  • 可以证明,无论如何,游戏都将胜利,因此不存在任何失败状态,答案为 00

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

  • 仅从网格状态上看,共有 44 种失败的可能性:$[2, 8, 4, 2], [2, 4, 8, 2], [4, 8, 4, 2],[2, 4, 8, 4]$。
  • 其中,[2,8,4,2][2, 8, 4, 2][2,4,8,2][2, 4, 8, 2] 分别对应 44 种本质不同的失败情况,[4,8,4,2][4, 8, 4, 2][2,4,8,4][2, 4, 8, 4] 分别对应 22 种本质不同的失败情况。
    • [2,8,4,2][2, 8, 4, 2] 为例,下面列举该局面对应的 44 种本质不同的失败情况(操作方式不唯一,数字上面的小数字表示出现时间):
    $$\begin{aligned} & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] & & [\overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}1\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}3\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}] & \stackrel{\text{R}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] & \stackrel{\text{R}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}4\hspace{3.84625mu}}{4}, \overset{\hspace{3.84625mu}7\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{\hspace{15.385mu}}{}, \overset{11}{2}] \\ \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{\hspace{15.385mu}}{}, \overset{13}{2}] & \stackrel{\text{R}}\to& [\overset{13}{2}, \overset{\hspace{15.385mu}}{}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{11}{2}, \overset{13}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{11}{2}, \overset{13}{2}] \\ \stackrel{\text{R}}\to& [\overset{15}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{13}{2}] & \stackrel{\text{L}}\to& [\overset{13}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{12}{4}, \overset{15}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}9\hspace{3.84625mu}}{2}, \overset{\hspace{3.84625mu}8\hspace{3.84625mu}}{8}, \overset{14}{4}, \overset{15}{2}] & \stackrel{\text{L}}\to& [\overset{\hspace{3.84625mu}5\hspace{3.84625mu}}{2}, \overset{10}{8}, \overset{14}{4}, \overset{15}{2}] \end{aligned} $$对这 44 种情况,出现时间的大小关系(离散化后)分别为 [4,1,2,3][4, 1, 2, 3][3,1,2,4][3, 1, 2, 4][2,1,3,4][2, 1, 3, 4][1,2,3,4][1, 2, 3, 4]
  • 所以,答案为 4+4+2+2=124 + 4 + 2 + 2 = 12,在模 7171 意义下为 1212

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

  • 可以证明答案为 3434,在模 7171 意义下为 3434

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

  • 可以证明答案为 162162,在模 7171 意义下为 2020

【样例 #2】

见附件中的 game/game2.ingame/game2.ans

该组样例满足测试点 353 \sim 5 的约束条件。

【样例 #3】

见附件中的 game/game3.ingame/game3.ans

该组样例满足测试点 6106 \sim 10 的约束条件。

【样例 #4】

见附件中的 game/game4.ingame/game4.ans

该组样例满足测试点 141714 \sim 17 的约束条件。

【样例 #5】

见附件中的 game/game5.ingame/game5.ans

该组样例满足测试点 222522 \sim 25 的约束条件。

【数据范围】

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

测试点编号 TT \le n,xn,x \le 特殊性质
121\sim2 1010 44
353\sim5 1010
6106\sim10 2222
111311\sim13 11 8080
141714\sim17 10001000
182018\sim20 11 300300
2121 10510^5 p=2p = 2
222522\sim25

对于全部数据,保证:1T1051\le T\le 10^51n,x3001\le n,x\le 3002p1092\le p\le10^9