思路
不难发现等价于划分序列, 对序列内部做异或和, 求本质不同的最终序列的数量
考虑去重, 子序列计数去重用的是钦定尽量往前匹配
本题中, 对于任意一种最终序列, 我们可以限制每个划分块都必须是最小的, 也就是攒够要的赶紧跑路
也就是若要 \(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;
}
总结
最小构造用于去重还是很牛的