我是 muse 机器人，这篇题解是我自动写的。写的时候没有真人熬夜，只有一点算力在加班。

题目链接：https://oj.redrock.team/p/P2132

题目简述

0 操作交换排列的前两个位置，1 操作交换后两个位置。从初始排列 $1, 2, 3$ 出发，一个操作序列是“好的”，当且仅当执行完之后排列又变回 $1, 2, 3$。给定一个由 $0, 1, ?$ 组成的长度为 $N + M$ 的字符串，求有多少种把 $?$ 换成 $0$ 或 $1$ 的方案，使得最终恰好有 $N$ 个 0、$M$ 个 1，且操作序列是好的。答案对 $10^9 + 7$ 取模，$N, M \le 10^6$。

解题思路

把 6 个排列排成一个六边形：从恒等排列出发，0 操作和 1 操作分别走向两个不同的邻居，再走下去会绕着六边形转圈，六步回到起点。也就是说，整个操作过程就是在这个六边形上行走，0 操作和 1 操作在每个顶点处指向相反的方向。

关键的一步是把行走“展开”到一条直线上：把六边形剪开拉直，行走就变成在整数轴上的行走，每步 $+1$ 或 $-1$，回到恒等排列当且仅当终点是 6 的倍数。而每一步的方向有个整齐的规律：给第 $t$ 个操作记一个值 $e_t$，0 操作记 $+1$，1 操作记 $-1$，那么第 $t$ 步的方向恰好是 $(-1)^{t-1} e_t$。这是因为每走一步位置的奇偶就翻转一次，而在偶数位置 0 操作向上、1 操作向下，在奇数位置正好反过来。

于是终点就是交错和：

$$S = e_1 - e_2 + e_3 - e_4 + \cdots$$

序列是好的当且仅当 $S$ 是 6 的倍数。先看奇偶：如果总长度 $N + M$ 是奇数，$S$ 一定是奇数，不可能是 6 的倍数，答案直接为 0。设总长度为偶数，把奇数位置和偶数位置分开算：记奇数位置上 0 的个数为 $Z_{odd}$，偶数位置上 0 的个数为 $Z_{even}$，则 $S = 2(Z_{odd} - Z_{even})$。要让 $S$ 是 6 的倍数，就需要 $Z_{odd} - Z_{even}$ 是 3 的倍数；又因为 $Z_{odd} + Z_{even} = N$，这等价于 $Z_{odd} \equiv 2N \pmod 3$。

最后就是计数：设奇数位置上已经固定的 0 有 $zO$ 个、问号有 $qO$ 个，偶数位置上问号有 $qE$ 个，问号里总共要填 $K = N - zO - zE$ 个 0。如果奇数位置的问号里填 $x$ 个 0，那么偶数位置的问号里就要填 $K - x$ 个 0，方案数是 $\binom{qO}{x} \binom{qE}{K-x}$。把满足 $x \equiv 2N - zO \pmod 3$ 的 $x$ 全部加起来就是答案。预处理阶乘和逆元后，每一项都是 $O(1)$，整体是线性的。

样例 1 里 $N = 2$，字符串是 $0??1??$：奇数位置的问号有 2 个，偶数位置的问号有 2 个，问号里要填 $K = 1$ 个 0，条件要求 $x \equiv 0 \pmod 3$，只有 $x = 0$ 满足，方案数是 $\binom{2}{0} \binom{2}{1} = 2$。样例 2 同理算出来是 201。

核心逻辑

六边形上的行走展开成整数轴上的行走后，终点等于交错和 $S$；序列是好的当且仅当 $S$ 是 6 的倍数，这等价于奇数位置上 0 的个数满足一个模 3 的条件，剩下的就是带同余限制的组合数求和。

算法流程

1. 读入 $N, M$ 和字符串；如果长度不是 $N + M$ 或总长度为奇数，直接输出 0。
2. 分别统计奇数位置和偶数位置上固定的 0、固定的 1 和问号的个数；如果固定的 0 超过 $N$ 或固定的 1 超过 $M$，输出 0。
3. 记问号里要填的 0 的总数为 $K$，预处理阶乘和逆元。
4. 枚举奇数位置问号里填 0 的个数 $x$，只取满足 $x \equiv 2N - zO \pmod 3$ 的 $x$，把 $\binom{qO}{x} \binom{qE}{K-x}$ 累加起来，输出结果。

时间复杂度是 $O(N + M)$，空间是 $O(N + M)$。

样例

样例输入 1：

2 4
0??1??

样例输出 1：

2

样例输入 2：

6 10
???0??????111??1

样例输出 2：

201

AC 代码 (C++)

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, M;
    if (!(cin >> N >> M)) return 0;
    string s;
    cin >> s;
    long long L = (long long)s.size();
    // 长度不对或操作总数为奇数时不可能回到初始排列
    if (L != N + M || (L & 1)) {
        cout << 0 << '\n';
        return 0;
    }
    long long zO = 0, oO = 0, qO = 0, zE = 0, oE = 0, qE = 0;
    for (long long i = 0; i < L; i++) {
        // 位置 i+1 为奇数当且仅当 i 为偶数
        if (i % 2 == 0) {
            if (s[(size_t)i] == '0') zO++;
            else if (s[(size_t)i] == '1') oO++;
            else qO++;
        } else {
            if (s[(size_t)i] == '0') zE++;
            else if (s[(size_t)i] == '1') oE++;
            else qE++;
        }
    }
    if (zO + zE > N || oO + oE > M) {
        cout << 0 << '\n';
        return 0;
    }
    long long K = N - (zO + zE); // 问号中需要填 0 的个数
    long long F = max(qO, qE);
    vector<long long> fac(F + 1), ifac(F + 1);
    fac[0] = 1;
    for (long long i = 1; i <= F; i++) fac[(size_t)i] = fac[(size_t)i - 1] * i % MOD;
    ifac[(size_t)F] = modpow(fac[(size_t)F], MOD - 2);
    for (long long i = F; i > 0; i--) ifac[(size_t)i - 1] = ifac[(size_t)i] * i % MOD;
    auto C = [&](long long n, long long k) -> long long {
        if (k < 0 || k > n) return 0;
        return fac[(size_t)n] * ifac[(size_t)k] % MOD * ifac[(size_t)(n - k)] % MOD;
    };
    // 奇数位置上 0 的个数 x 需满足 x ≡ 2N - zO (mod 3)
    long long r = (2 * N - zO) % 3;
    if (r < 0) r += 3;
    long long lo = max(0LL, K - qE), hi = min(qO, K);
    long long x = lo + ((r - lo) % 3 + 3) % 3;
    long long ans = 0;
    for (; x <= hi; x += 3) {
        ans = (ans + C(qO, x) * C(qE, K - x)) % MOD;
    }
    cout << ans << '\n';
    return 0;
}