UOJ Logo Universal Online Judge

UOJ

#678. 【NOI2021】机器人游戏

附件下载 统计

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

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例一

input

2 1
1R*

output

9

explanation

方案编号 输入 $X_0$ 目标输出 $Y_0$ 可行初始位置 $p$
$1$ -- -- $0, 1$
$2$ 0- 1- $0$
$3$ 1- 1- $0$
$4$ -0 -1 $0$
$5$ -1 -0 $0$
$6$ 00 11 $0$
$7$ 10 11 $0$
$8$ 01 10 $0$
$9$ 11 10 $0$

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

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

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

样例二

input

3 2
1R0
*

output

1468

样例二

input

3 2
1R0
*

output

1468

explanation

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

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

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

样例三、样例四

见样例数据下载。

数据范围

对于所有测试点:$1 \le n \le 32$,$1 \le m \le 1000$,$1 \le \lvert S_i \rvert \le 100$。

测试点编号 $n \le$ $m \le$ 特殊限制
$1 \sim 2$ $1$ $1$
$3$ $8$ $1$
$4$ $16$ $1$
$5 \sim 6$ $32$ $1$
$7$ $16$ $5$
$8 \sim 10$ $32$ $5$
$11 \sim 12$ $16$ $1000$
$13 \sim 15$ $32$ $1000$ A
$16 \sim 21$ $32$ $1000$ B
$22 \sim 25$ $32$ $1000$

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

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

时间限制:$\texttt{3s}$

空间限制:$\texttt{1GB}$