思路

不難發現等價于劃分序列, 對序列內部做異或和, 求本質不同的最終序列的數量

考慮去重, 子序列計數去重用的是欽定盡量往前匹配
本題中, 對于任意一種最終序列, 我們可以限制每個劃分塊都必須是最小的, 也就是攢夠要的趕緊跑路
也就是若要 \(1\), 就找到后面第一個 \(1\) 劃分, 若要 \(0\), 就找直接一個 \(0\) 或者連續兩個 \(1\)
然后最后找任意結尾, 加上最后一段算方案數

#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e6 + 20;
const int MOD = 998244353;

int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }

int a[MAXN];
int f[MAXN];
int nxt1[MAXN];
std::unordered_set<long long> vis;
signed main() {
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    int _; scanf("%lld", &_);
    while (_--) {
        std::string astr; std::cin >> astr;
        int n = astr.size();
        bool sp = true;
        for (int i = 1; i <= n; i++) a[i] = astr[i - 1] - '0', sp &= (a[i] == 1);
        a[n + 1] = 1; a[n + 2] = 1;

        /*找每個位置后第一個 1*/
        for (int i = n + 2; i >= 1; i--) {
            if (a[i]) nxt1[i] = i;
            else nxt1[i] = nxt1[i + 1];
        }
        /*dp*/
        f[0] = 1;
        for (int i = 1; i <= n; i++) f[i] = 0;
        for (int i = 0; i <= n; i++) {
            if (a[i + 1]) {
                if (i + 1 <= n) f[i + 1] = add(f[i + 1], f[i]);
            }
            else {
                if (nxt1[i + 1] <= n) f[nxt1[i + 1]] = add(f[nxt1[i + 1]], f[i]);
            }

            if (!a[i + 1]) {
                if (i + 1 <= n) f[i + 1] = add(f[i + 1], f[i]);
            }
            else {
                if (nxt1[nxt1[i + 1] + 1] <= n) f[nxt1[nxt1[i + 1] + 1]] = add(f[nxt1[nxt1[i + 1] + 1]], f[i]);
            }
        }

        int ans = 0;
        for (int i = 0; i <= n - 1; i++) {
            ans = add(ans, f[i]);
        }
        printf("%lld\n", ans);
    }

    return 0;
}

總結

最小構造用于去重還是很牛的