问题本质

给定 $m$ 个机器人在长度为 $n$ 的纸带上的操作序列，每个操作是 R（右移）、0（写0）、1（写1）、*（取反）之一。要求统计满足以下条件的输入输出组合数：

存在一个公共的起始位置 $p$，使得所有机器人：

从 $p$ 开始执行操作不会爆炸（不会移出纸带右边界）

执行完操作后，纸带状态等于给定的输出

核心思路

1.问题转化

对于固定的起始位置 $p$，每个机器人的执行轨迹是确定的。问题转化为：对每个可能的 $p$，计算能产生合法输入输出组合的机器人集合，然后用容斥原理统计所有 $p$ 的并集。

2.关键观察

纸带格子状态：0、1、-（空）

输入输出组合：每个格子有 $3 \times 3 = 9$ 种可能（输入状态 × 输出状态）

但实际合法的输入输出对受到机器人操作的约束

3.状态表示

对于每个机器人 $i$ 和起始位置 $p$，可以预处理出：

哪些格子会被访问（S[0][i][p] 等）

每个被访问格子的操作类型（mov[i][j]）

用位掩码表示格子的访问情况和操作约束。

4.算法框架

预处理：计算每个机器人在每个起始位置的操作影响

分治容斥：

• 前半段位置（$1$ 到 $n/2$）：直接枚举位置集合，用位运算快速计算

• 后半段位置（$n/2+1$ 到 $n$）：使用动态规划 + 容斥

合并答案：用容斥原理避免重复计数

复杂度分析

预处理：$O(m \cdot n^2)$

前半段处理：$O(n \cdot 2^{n/2} \cdot m)$

后半段处理：$O(n \cdot 2^{n/2} \cdot m)$

总复杂度：$O(n \cdot 2^{n/2} \cdot m)$，在 $n \le 32$ 时可接受

总结

本题通过容斥原理 + 位运算优化 + 分治策略，解决了机器人操作序列的计数问题。关键点在于：

将位置选择问题转化为集合覆盖问题

用位掩码高效表示操作约束

分治处理降低指数复杂度

动态规划处理后半段位置选择

算法充分利用了 $n$ 较小的特点，通过精巧的状态设计和位运算优化，在合理时间内解决了问题。

AC代码

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n, m, N, M, len, inall, U;
long long Ans, val;
int mov[1010][110], r[1010], Inall[110];
long long S[5][1010][40], V[(1 << 16) | 5];
long long pw2[1010], pw3[1010];
bitset<1010> F[4][(1 << 17) | 5], all, All[40], B1, B2;
long long f[40][(1 << 16) | 5][2];
char s[1010];
void Getval(int j, long long S, int R) {
    S |= (1LL << (R - 1));

    for (int i = 1; i <= m; ++i) {
        if (R + r[i] > n)
            continue;

        int s0 = (::S[0][i][j])&S;
        int s1 = (::S[1][i][j])&S;
        int s2 = (::S[2][i][j])&S;
        int s3 = (::S[3][i][j])&S;

        if ((s0 && s1) || (s2 && s3))
            continue;

        if ((s0 || s1) && (s2 || s3))
            val = (val * 2) % mod;
        else
            val = val * 3 % mod;
    }

    return;
}
long long Getval1(int S, int ty) {
    if (ty) {
        B1 = (F[1][S]) | (F[2][S] & F[3][S]);
        B1 &= all;
        B2 = (F[2][S] | F[3][S]);
        B2 = B2 & (all ^ B1);
    } else {
        B1 = (F[0][S] & F[1][S]) | (F[2][S] & F[3][S]);
        B1 &= all;
        B2 = (F[0][S] | F[1][S]) & (F[2][S] | F[3][S]);
        B2 = B2 & (all ^ B1);
    }

    int c1 = B1.count(), c2 = B2.count();
    return pw2[c2] * pw3[inall - c1 - c2] % mod;
}
long long Getval2(int S, int ty) {
    if (ty) {
        B1 = (F[1][S]) | (F[2][S] & F[3][S]);
        B2 = (F[2][S] | F[3][S]);
        B2 = B2 & (all ^ B1);
    } else {
        B1 = (F[0][S] & F[1][S]) | (F[2][S] & F[3][S]);
        B2 = (F[0][S] | F[1][S]) & (F[2][S] | F[3][S]);
        B2 = B2 & (all ^ B1);
    }

    int c1 = B1.count(), c2 = B2.count();
    return pw2[c2] * pw3[inall - c1 - c2] % mod;
}
int main() {
    //freopen("robot.in", "r", stdin);
    //freopen("robot.out", "w", stdout);
    scanf("%d%d", &n, &m);
    pw2[0] = pw3[0] = 1;

    for (int i = 1; i <= m; ++i)
        pw2[i] = pw2[i - 1] * 2 % mod;

    for (int i = 1; i <= m; ++i)
        pw3[i] = pw3[i - 1] * 3 % mod;

    for (int i = 1; i <= m; ++i) {
        scanf("%s", s + 1);
        len = strlen(s + 1);
        ++M;
        r[M] = 0;

        for (int j = 1; j <= len; ++j) {
            if (s[j] == '0')
                mov[M][r[M]] = 2;

            if (s[j] == '1')
                mov[M][r[M]] = 3;

            if (s[j] == '*')
                mov[M][r[M]] ^= 1;

            if (s[j] == 'R')
                ++r[M];

            if (r[M] >= n)
                break;
        }

        if (r[M] >= n) {
            r[M] = 0;
            memset(mov[M], 0, sizeof(mov[M]));
            --M;
        }
    }

    m = M, M = 0;

    for (int k = 1; k <= m; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i < j)
                    S[0][k][i] |= (1ll << (j - 1));
                else
                    S[mov[k][i - j]][k][i] |= (1ll << (j - 1));
            }
        }
    }

    N = n / 2;

    for (int S = 0; S < (1 << N); ++S)
        V[S] = 1;

    for (int R = 1; R <= N; ++R) {
        for (int i = 1; i <= m; ++i) {
            if (R + r[i] > n)
                All[R][i] = 0;
            else ++Inall[R], All[R][i] = 1;
        }
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= m; ++j) {
                F[0][(1 << (i - 1))][j] = 0;
                F[1][(1 << (i - 1))][j] = 0;
                F[2][(1 << (i - 1))][j] = 0;
                F[3][(1 << (i - 1))][j] = 0;

                if (k < i)
                    F[0][(1 << (i - 1))][j] = 1;
                else
                    F[mov[j][k - i]][(1 << (i - 1))][j] = 1;
            }
        }

        for (int S = 0; S < (1 << N); ++S) {
            F[0][S] = F[0][S & (-S)] | F[0][S ^ (S & (-S))];
            F[1][S] = F[1][S & (-S)] | F[1][S ^ (S & (-S))];
            F[2][S] = F[2][S & (-S)] | F[2][S ^ (S & (-S))];
            F[3][S] = F[3][S & (-S)] | F[3][S ^ (S & (-S))];
        }

        for (int S = 0; S < (1 << N); ++S) {
            int R = 0;

            for (int i = 1; i <= n; ++i) {
                if (S >> (i - 1) & 1)
                    R = i;
            }

            all = All[R], inall = Inall[R];
            V[S] = V[S] * Getval1(S, 0) % mod;
        }
    }

    for (int S = 1; S < (1 << N); ++S) {
        if (__builtin_popcount(S) & 1)
            Ans += V[S];
        else
            Ans -= V[S];
    }

    Ans = (Ans % mod + mod) % mod;

    for (int R = n / 2 + 1; R <= n; ++R) {
        N = n - R, U = (1 << N) - 1, inall = 0;

        for (int i = 1; i <= m; ++i) {
            if (R + r[i] > n)
                all[i] = 0;
            else ++inall, all[i] = 1;
        }

        for (int i = 1; i <= N + 1; ++i) {
            for (int j = 1; j <= m; ++j) {
                F[0][(1 << (i - 1))][j] = 0;
                F[1][(1 << (i - 1))][j] = 0;
                F[2][(1 << (i - 1))][j] = 0;
                F[3][(1 << (i - 1))][j] = 0;

                if (R + r[j] > n)
                    continue;

                F[mov[j][i - 1]][(1 << (i - 1))][j] = 1;
            }
        }

        for (int S = 0; S < (1 << (N + 1)); ++S) {
            F[0][S] = F[0][S & (-S)] | F[0][S ^ (S & (-S))];
            F[1][S] = F[1][S & (-S)] | F[1][S ^ (S & (-S))];
            F[2][S] = F[2][S & (-S)] | F[2][S ^ (S & (-S))];
            F[3][S] = F[3][S & (-S)] | F[3][S ^ (S & (-S))];
        }

        f[0][0][0] = 1;

        for (int i = 1; i < R; ++i) {
            for (int S = 0; S < (1 << N); ++S)
                f[i][S][0] = f[i][S][1] = 0;

            for (int S = 0; S < (1 << N); ++S) {
                if (f[i - 1][S][0] || f[i - 1][S][1]) {
                    int T = S << 1, o = 0;
                    val = Getval2(T, 1);
                    o = (T > U);
                    T &= U;
                    f[i][T][o] = (f[i][T][o] + f[i - 1][S][0] * val) % mod;
                    f[i][T][1] = (f[i][T][1] + f[i - 1][S][1] * val) % mod;

                    T = S << 1 | 1, o = 0;
                    val = Getval2(T, 1);
                    o = (T > U);
                    T &= U;
                    f[i][T][o] = (f[i][T][o] - f[i - 1][S][0] * val) % mod;
                    f[i][T][1] = (f[i][T][1] - f[i - 1][S][1] * val) % mod;

                    if (f[i][T][o] < 0)
                        f[i][T][o] += mod;

                    if (f[i][T][1] < 0)
                        f[i][T][1] += mod;
                }
            }
        }

        for (int S = 0; S < (1 << N); ++S) {
            if (f[R - 1][S][0]) {
                int T = S, o = 0;
                val = 1;

                for (int i = R; i <= n; ++i) {
                    T = (T << 1) | (i == R);
                    val = val * Getval2(T, o) % mod;
                    o |= (T > U);
                    T &= U;
                }

                Ans = (Ans + f[R - 1][S][0] * val) % mod;
            }

            if (f[R - 1][S][1]) {
                int T = S;
                val = 1;

                for (int i = R; i <= n; ++i) {
                    T = (T << 1) | (i == R);
                    val = val * Getval2(T, 1) % mod;
                    T &= U;
                }

                Ans = (Ans + f[R - 1][S][1] * val) % mod;
            }
        }
    }

    printf("%lld\n", Ans);
    return 0;
}