题解 | #Balanced 01-String#

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
char s[N];
int f[N][2][2]; // f[i][j][k]为考虑前i个字符, 相邻两个元素相同的对数奇偶性为j, 且第i个元素为k的方案数
int main() {
    int T;
    cin >> T;
    while (T --) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        memset(f, 0, sizeof f);
        if (s[1] == '0') f[1][0][0] = 1;
        else if (s[1] == '1') f[1][0][1] = 1;
        else f[1][0][0] = f[1][0][1] = 1;
        for (int i = 2; i <= n; i ++) {
            if (s[i] == '0') {
                f[i][0][0] = (f[i - 1][0][1] + f[i - 1][1][0]) % mod;
                f[i][1][0] = (f[i - 1][1][1] + f[i - 1][0][0]) % mod;
            } else if (s[i] == '1') {
                f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][1]) % mod;
                f[i][1][1] = (f[i - 1][1][0] + f[i - 1][0][1]) % mod;
            } else {
                f[i][0][0] = (f[i - 1][0][1] + f[i - 1][1][0]) % mod;
                f[i][1][0] = (f[i - 1][1][1] + f[i - 1][0][0]) % mod;
                f[i][0][1] = (f[i - 1][0][0] + f[i - 1][1][1]) % mod;
                f[i][1][1] = (f[i - 1][1][0] + f[i - 1][0][1]) % mod;
            }
        }
        printf("%d\n", (f[n][0][0] + f[n][0][1]) % mod);
    }
    return 0;
}