#1859. 「NOI2021」机器人游戏

「NOI2021」机器人游戏

题目描述

小 R 有 mm1m10001 \le m \le 1000)个机器人和 mm 张纸带,第 ii1im1 \le i \le m)个机器人负责对第 ii 张纸带进行操作。对于每张纸带,它们都被从左到右分成了 nn1n321 \le n \le 32)个格子,依次编号为 0,1,,n10, 1, \ldots , n - 1。每个格子有 33 种状态:1. 格子上写有数字 00;2. 格子上写有数字 11;3. 格子是一个空格子。

在任意时刻,机器人必须站在纸带上的一个格子中。在设定好机器人在纸带上的初始位置后,第 ii 个机器人会依次执行预先设定的操作序列 SiS_i,操作由 R01* 四种字符组成,其中:

  1. R 表示机器人向右走一格,如果右边没有格子,则机器人会原地爆炸;
  2. 0 表示如果机器人所在格子非空,则将该格子上的数字改为 00,否则不修改;
  3. 1 表示如果机器人所在格子非空,则将该格子上的数字改为 11,否则不修改;
  4. * 表示如果机器人所在格子非空,则将格子上的数字 xx 改为 1x1 - x,否则不修改。

ii 张纸带的状态可以用一个长度为 nn 的序列表示,每个元素为 01-(空格子),依次表示其每个格子的状态。第 ii 张纸带的初始状态称为机器人 ii 的输入 XiX_i,操作执行完成后纸带的状态称为机器人 ii 的输出 YiY_i。注意,如果机器人爆炸了,那么这个机器人就没有输出。

可以发现,如果一个格子为空,那么机器人永远不会修改它。所以每个机器人都有如下特性:如果第 ii 个机器人所在的纸带上的所有格子都为空,那么它就不会执行任何操作,它的输出即为所有格子都为空。

现在小 R 给定了每一个机器人的输入 XiX_i(即每张纸带的初始状态)以及目标输出 YiY_i。小 R 希望小 D 找到一个位置 pp0p<n0 \le p < n),使得所有机器人都能以其所在纸带的第 pp 个格子为初始位置,在不爆炸的情况下执行完所有操作,并且满足第 ii 个机器人的输出为 YiY_i

小 D 花了几毫秒解决了问题,现在他想知道,有多少个输入和输出的组合方式使得上述问题有解,即有多少种为每个机器人设定输入 X0,X1,,Xm1X_0, X_1, \ldots , X_{m - 1} 和目标输出 Y0,Y1,,Ym1Y_0, Y_1, \ldots , Y_{m - 1} 的方式,使得至少存在一个位置 pp0p<n0 \le p < n),使得所有机器人都能以其所在纸带的第 pp 个格子为起点,在不爆炸的情况下执行完所有操作,且满足第 ii 个机器人的输出为 YiY_i。请你帮助小 D 解决这个问题,由于最终的答案可能很大,请你输出答案对 109+7{10}^9 + 7 取模后的余数。

两个组合方式不同当且仅当,存在至少一个机器人,它的输入或是目标输出在两个方式中不同。

输入格式

第一行包含两个正整数 n,mn, m,分别表示每张纸带上的格子数和纸带数量。

接下来 mm 行,第 ii 行输入一个仅包含 R 0 1 * 这四种字符的字符串 SiS_i,表示第 ii 个机器人的操作序列。

输出格式

仅一行一个正整数,表示答案模 109+7{10}^9 + 7 后的余数。

样例 1

2 1
1R*

9

方案编号 输入 X0X_0 目标输出 Y0Y_0 可行初始位置 pp
11 -- -- 0,10, 1
22 0- 1- 00
33 1- 1-
44 -0 -1
55 -1 -0
66 00 11
77 10 11
88 01 10
99 11 10

表中 - 表示空格子。注意方案 11 的输入和输出中有两个空格子。

当输入全为空时,初始位置可以是 0011,因为根据题意,输入全为空时机器人不会执行任何操作。

当输入不全为空时,初始位置只能为 00,如果初始位置为 11 机器人一定会爆炸。所以此时实际执行的操作是将第一格的数字改为 11,并将第二格的数字 xx 改为 1x1 - x

3 2
1R0
*

1468

可以用容斥原理来计算这个样例。

  1. 初始位置 p=0p = 0 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带 00 号格子要么输入输出都是空,要么目标输出是 11(输入无所谓),所以有 33 种方案;11 号格子要么输入输出都是空,要么目标输出是 00,也是 33 种方案;22 号格子要么输入输出都是空,要么输入和目标输出相同(因为没有对该格子执行任何操作),同样是 33 种方案,共 2727 种方案。第二个机器人的 00 号格子要么输入输出都是空,要么输入和目标输出不同,是 33 种方案,11 号和 22 号格子也都是 33 种方案,共 2727 种方案。所以总共 27×27=72927 \times 27 = 729 种方案。
  2. 初始位置 p=1p = 1 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带三个格子都是 33 种方案,其中 00 号格子要么输入输出都为空,要么相同;11 号格子要么输入输出都为空,要么目标输出是 1122 号格子的输入输出要么都为空,要么输出是 00,共 2727 种方案。第二个机器人的 11 号格子要么输入输出都是空,要么输入和目标输出不同,是 33 种方案;00 号和 22 号格子要么输入输出都为空,要么输入输出相同,也都是 33 种方案,共 2727 种方案。总共 27×27=72927 \times 27 = 729 种方案。
  3. 初始位置 p=2p = 2 可以使得执行完所有操作后满足条件。那么第一个机器人的纸带必须输入输出全为空(否则爆炸),只有 11 种方案。第二个机器人是 2727 种方案,总共 2727 种方案。
  4. 初始位置 p=0,1p = 0, 1 都满足条件。这要求第一个机器人的 11 号格子输入输出都为空;00 号格子的输入输出都为空或都为 1122 号格子的输入输出都为空或都为 00,所以第一个机器人的纸带有 44 种方案。第二个机器人 00 号格子和 11 号格子都为空,22 号格子有 33 种方案,第二个机器人的 00 号和 11 号格子必须都为空,22 号格子要么输入输出都为空,要么输入和输出相同,有 33 种方案。总共 1212 种方案。
  5. 初始位置 p=0,2p = 0, 2 都满足条件。那么第一个机器人的纸带必须输入输出全为空(否则爆炸),只有 11 种方案。第二个机器人 00 号和 22 号格子都为空,11 号格子有 33 种方案。总共 33 种方案。
  6. 初始位置 p=1,2p = 1, 2 都满足条件。那么第一个机器人的纸带必须输入输出全为空,只有 11 种方案。第二个机器人 11 号和 22 号格子都为空,00 号格子有 33 种方案。总共 33 种方案。
  7. 初始位置 p=0,1,2p = 0, 1, 2 都满足条件。那么两个机器人的输入输出必须都为空,总共 11 种方案。

根据容斥原理,最后的答案为 729+729+271233+1=1468729 + 729 + 27 - 12 - 3 - 3 + 1 = 1468

样例 3

见附加文件中的 robot/robot3.inrobot/robot3.ans

样例 4

见附加文件中的 robot/robot4.inrobot/robot4.ans

数据范围与提示

对于所有测试点:1n321 \le n \le 321m10001 \le m \le 10001Si1001 \le \lvert S_i \rvert \le 100

测试点编号 nn \le mm \le 特殊限制
121 \sim 2 11 11
33 88
44 1616
565 \sim 6 3232
77 1616 55
8108 \sim 10 3232
111211 \sim 12 1616 10001000
131513 \sim 15 3232 A
162116 \sim 21 B
222522 \sim 25

特殊限制 A:操作序列中不存在 R

特殊限制 B:每个操作序列中,R 的数量至多 1515 个。