【题解】「NOI2021」机器人游戏 容斥 + 状压 DP + 数据分治 + bitset — Qiuly

该做法不是官方做法。

对于 $n\leq16$ 的部分分可以参考样例解释，直接容斥。

即考虑枚举一定满足的起点集合 $P$。对于某个机器人 $i$，令 $C_{i,j,0/1}$ 表示机器人 $i$，起点为 $p$ 时，如果最开始 $p+j$ 上是 $0/1$，得到的结果是多少。

那么计算此时的方案数，可以枚举每个机器人，然后考虑最后每个格子的贡献，如果从起点集合 $P$ 出发，第 $i$ 个机器人走到第 $j$ 个格子，最开始第 $j$ 个格子为 $0/1$ 时，得到的结果并非全为 $0$ 或 $1$，就意味着没办法选择一个第 $j$ 个格子的最终值，使得所有机器人合法，否则意味着有唯一一种最终值的选择使其合法。

这下就有了 $28$ 分（参考 solve1 部分）。接着考虑 $n\leq 32$ 的部分，发现有一档特殊性质叫做” 每个操作序列中，R 的数量至多 15 个”，也就是说一个起点 $p$ 影响的格子只包括最多 $16$ 个，这启发我们用 dp 解决这一部分，即从左至右每个格子，记录最近的一些格子是否被作为起点即可。

此时我们获得了 $48$ 分。注意到因为计算贡献的时候枚举了每个机器人，所以此时复杂度是和 $m$ 相关的，怎么继续优化呢？

首先从原来的方法，推出每个机器人对每个格子的贡献的新的表达式。因为可以发现，计算贡献的时候，其实就是要求 $C_{i,j,0/1}$ 中的若干位置（集合 $T$），取值是否相同，考虑用 $S_{i,0}$ 表示 $C_{i,j,0}$ 中取到 $0$ 的集合，最后要求的就是 $S_{i,0}$ 是否是 $T$ 的超集，又或者 $S_{i,0}$ 和 $T$ 的交集是否为空（$S_{i,1}$ 类似，当然还有一些需要讨论的细节，在此就不展开了）。

以”$S_{i,0}$ 是否是 $T$ 的超集” 为例，实际要求的是” 多少个 $i$ 满足 $S_{i,0}$ 是 $T$ 的超集”，事实上，因为 $S_{i,0}$ 和 $S_{i,1}$ 的贡献没办法用简单的乘法合并，最终要求的其实是” 哪些 $i$ 满足 $S_{i,0}$ 是 $T$ 的超集”。

用 bitset 维护即可。同时因为如果给 $S_{i,0}$ 简单标号的话会有 $0\leq S_{i,0}< 2^{32}$，bitset 维护信息的时候还需要将值域分块。这样下来总共要维护 $2^{n+3}$ 个 bitset，常数略大，具体实现的时候需要简单的剪枝和卡常。

跑的也不算慢。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef std :: pair <int, int> pii;

#define fi first
#define se second
#define pb push_back
#define mkp std :: make_pair
#define ep emplace_back

#define Lep(i, l, r) for (int i = l; i < r; ++ i)
#define Rep(i, r, l) for (int i = r; i > l; -- i)
#define lep(i, l, r) for (int i = l; i <= r; ++ i)
#define rep(i, r, l) for (int i = r; i >= l; -- i)

char _c; bool _f; template <class T> inline void IN (T & x) {
    x = 0, _f = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
    while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = -x;
}

const int mod = 1e9 + 7;

inline int mul (int x, int y) { return 1ll * x * y % mod; }
inline void sub (int &x, int y) { x -= y; if (x < 0) x += mod; }
inline void pls (int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline int dec (int x, int y) { x -= y; if (x < 0) x += mod; return x; }
inline int add (int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
inline int modpow (int x, ll y, int res = 1) {
    for (y = (y + mod - 1) % (mod - 1); y; y >>= 1, x = mul (x, x)) if (y & 1) res = mul (x, res);
    return res;
}

template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }

const int N = 32 + 5;
const int M = 1e3 + 5;
const int NL = 1e2 + 5;
const int NS = (1 << 16) | 5;
const uint pall = (1 << 16) - 1;
const int Dlim = 16;

int n, m, pw2[M], pw3[M], Rsiz[M], pre[NS][N][2], dp[N][NS][N][2];
bitset <M> Tmp[3], PosSta[2][2][2][NS];
uint ChangeRule[M][2];
char str[NL];

inline void prework () {
    IN (n), IN (m);
    pw2[0] = pw3[0] = 1;
    lep (i, 1, m) pw2[i] = mul (pw2[i - 1], 2), pw3[i] = mul (pw3[i - 1], 3);

    lep (t, 1, m) {
        scanf ("%s", str + 1), Rsiz[t] = -1;
        int len = strlen (str + 1);

        for (int l = 0, r; l <= len; l = r + 1) {
            r = l;
            while (r < len && str[r + 1] != 'R') ++ r;

            int s0 = 0, s1 = 1;
            lep (i, l + 1, r)
                if (str[i] == '*') s0 ^= 1, s1 ^= 1;
                else s0 = s1 = str[i] - '0';
            ++ Rsiz[t], ChangeRule[t][0] |= (! s0) << Rsiz[t], ChangeRule[t][1] |= s1 << Rsiz[t];
        }
        Lep (i, Rsiz[t] + 1, n) ChangeRule[t][0] |= 1 << i, ChangeRule[t][1] |= 1 << i;
    }
}

inline void getB (const int o, const uint &S, const int rlt) {
    Tmp[rlt] = (PosSta[0][o][0][S & pall] & PosSta[0][o][1][S >> 16]) |
               (PosSta[1][o][0][pall ^ (S & pall)] & PosSta[1][o][1][pall ^ (S >> 16)]);
}
inline int query1 (const uint &S) {
    getB (0, S, 0), getB (1, S, 1);
    Tmp[2] = Tmp[0] & Tmp[1];
    return mul (pw3[Tmp[2].count ()], pw2[Tmp[0].count () + Tmp[1].count () - 2 * Tmp[2].count ()]);
}
inline int query0 (const uint &S, const bool typ) {
    Tmp[0] = typ ? (PosSta[0][0][0][S] | PosSta[1][0][0][pall ^ S]) : PosSta[0][0][0][S];
    Tmp[1] = typ ? (PosSta[0][1][0][S] | PosSta[1][1][0][pall ^ S]) : PosSta[0][1][0][S];
    Tmp[2] = Tmp[0] & Tmp[1];
    return mul (pw3[Tmp[2].count ()], pw2[Tmp[0].count () + Tmp[1].count () - 2 * Tmp[2].count ()]);
}

// 分三个 insert 其实就是剪枝
inline void insert0 (const int & i) {
    uint S, T;
    lep (o, 0, 1) {
        const uint now = ChangeRule[i][o], val1 = now & pall;

        T = S = val1; while (true) { PosSta[0][o][0][T].set (i); if (! T) break; T = S & (T - 1); }
        T = S = pall ^ val1; while (true) { PosSta[1][o][0][val1 ^ T].set (i); if (! T) break; T = S & (T - 1); }
    }
}
inline void insert1 () {
    uint S, T;
    lep (o, 0, 1) {
        T = S = pall; while (true) { PosSta[0][o][1][T] |= Tmp[0]; if (! T) break; T = S & (T - 1); }
        T = S = 0; while (true) { PosSta[1][o][1][pall ^ T] |= Tmp[0]; if (! T) break; T = S & (T - 1); }
    }
}
inline void insert2 (const int &i) {
    uint S, T;
    lep (o, 0, 1) {
        const uint now = ChangeRule[i][o], val1 = now & pall, val2 = now >> 16;

        T = S = val1; while (true) { PosSta[0][o][0][T].set (i); if (! T) break; T = S & (T - 1); }
        T = S = pall ^ val1; while (true) { PosSta[1][o][0][val1 ^ T].set (i); if (! T) break; T = S & (T - 1); }
        T = S = val2; while (true) { PosSta[0][o][1][T].set (i); if (! T) break; T = S & (T - 1); }
        T = S = pall ^ val2; while (true) { PosSta[1][o][1][val2 ^ T].set (i); if (! T) break; T = S & (T - 1); }
    }
}
int main () {
    freopen ("robot.in", "r", stdin);
    freopen ("robot.out", "w", stdout); 
    prework ();

    int ans = 0;
    const int nlim = min (n, Dlim), Slim = (n <= Dlim) ? 0 : (1 << n - Dlim);

    Lep (j, 0, n - nlim) {
        lep (i, 1, m) if (Rsiz[i] == j) insert0 (i);
        Lep (S, 0, Slim) pre[S][j][0] = query0 (S, 1), pre[S][j][1] = query0 (S, 0);
    }
    lep (i, 1, m) if (Rsiz[i] < n - nlim) Tmp[0].set (i);
    insert1 ();

    rep (mxpos, nlim - 1, 0) {
        lep (i, 1, m) if (Rsiz[i] == n - mxpos - 1) insert2 (i);

        const int Tlim = 1 << mxpos;
        Lep (T, Tlim, Tlim << 1) {
            int res = 1, szpos = 1;
            Lep (j, 0, mxpos) if ((T >> j) & 1) ++ szpos;

            uint tool = 0;
            Lep (j, 0, nlim) tool = (tool << 1) | ((T >> j) & 1), res = mul (res, query0 (tool, j >= mxpos));
            Lep (j, nlim, n) tool <<= 1, res = mul (res, query1 (tool));
            pls (ans, mul (res, (szpos & 1) ? 1 : mod - 1));
        }
    }
    if (n <= Dlim) return printf ("%d\n", ans), 0;

    Lep (i, 0, n) {
        const int Tlim = 1 << min (i, n - Dlim);

        Lep (T, 0, Tlim) lep (Ci, 0, 1) {
            const int S = ((T << 1) & (Slim - 1)) + Ci;

            Lep (np, Dlim, n) if (! ((S & 1) && (np < i))) lep (lo, 0, 1) {
                const int no = lo | ((T >> n - Dlim - 1) & 1);
                int lst = mul ((i ? dp[i - 1][T][np][lo] : (lo ? 0 : mod - 1)), pre[S][n - np - 1][np > i || no]);
                pls (dp[i][S][np][no], (S & 1) ? mod - lst : lst);
            }
        }
    }
    Lep (S, 1, Slim) {
        int mxpos = 0;
        rep (i, n - Dlim - 1, 0) if ((S >> i) & 1) mxpos = n - 1 - i;
        if (mxpos >= Dlim) pls (ans, add (dp[n - 1][S][mxpos][0], dp[n - 1][S][mxpos][1]));
    }
    printf ("%d\n", ans);
    return 0;
}