CF1383E Strange Operation
好题啊！！
观察一下这个操作的本质：每次选择相邻两个位置，如果有 0 会直接消掉一个 0，否则消掉一个 1。
这启发我们根据 1 的数量来做题。
如果把相邻两个 1 之间的 0 的数量记录下来，那么会形成一个序列与 01 串一一对应，记这个序列为 \(a\)，原串对应序列为 \(b\)。现在操作变成对这个序列中某个位置减一或者消掉不是首尾的一个 0。
首尾可以单独考虑，先给答案乘上 \((a_1 + 1) (a_n + 1)\)。接下来思考合法的最终序列满足什么条件。
显然，最终序列合法当且仅g当存在 \(1 \le i_1 \le i_2 \le ... \le i_{|a|} \le |b|\)，使得\(a_{i} \le b_{i_k}\)。
可以直接考虑 DP，设 \(f_k\) 表示最后的一个 \(i\) 是 \(k\) 的方案数，答案就是 \(\sum f_k\)。转移比较简单，可以用单调栈优化，最终复杂度 \(O(n)\)。
怠码
#include <cstdio>
#include <iostream>
#include <cstring>
#define LL long lon
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const LL P = 1e9 + 7;
const int N = 1e6 + 10;
char s[N];
int len, n;
int stk[N], top;
LL f[N], a[N], pre[N];
int main() {
scanf("%s",s + 1);
len = strlen(s + 1);
int cnt = 0;
for(int i = 1; i <= len; ++i) {
if(s[i] == '0') ++cnt;
else a[++n] = cnt, cnt = 0;
}
a[++n] = cnt;
if(n == 1) {
printf("%lld\n",a[1]);
return 0;
}
LL mul = (a[1] + 1) * (a[n] + 1) % P;
for(int i = 1; i < n; ++i)
a[i] = a[i + 1];
n -= 2;
f[0] = 1, pre[0] = 1, stk[++top] = 0;
for(int i = 1; i <= n; ++i) {
stk[top + 1] = i;
f[i] = f[i - 1] * (a[i] + 1) % P;
while(top && a[stk[top]] <= a[i])
f[i] = (f[i] + (a[i] - a[stk[top]]) *
((stk[top] == 0 ? 0 : pre[stk[top] - 1])
- (top == 1 ? 0 : pre[stk[top - 1] - 1]) + P) % P) % P,
--top;
pre[i] = (pre[i - 1] + f[i]) % P;
stk[++top] = i;
}
printf("%lld\n",pre[n] * mul % P);
}