\(\large\mathcal{Description}\)
定义一个长度为奇数 \(n\) 的 \(01\) 串为美丽的，当且仅当每次将连续 \(3\) 个位替换为它们的中位数 \(\dfrac{n-1}2\) 次后，这个串变成一个字符 \(1\).
现在给定由 \(0, 1, ?\) 三种字符组成的字符串 \(S\)，求：将每个问号替换为 \(0/1\) 后，得到一个美丽的字符串的方案数，答案对 \(10^9+7\) 取模。
\(1 \le n \le 3\times 10^5\).
\(\large\mathcal{Solution}\)
如果我们已经将所有 \(?\) 填好了，如何判断得到的 \(S\) 是否是美丽的？
由于操作是“将连续 \(3\) 个位替换为它们的中位数”，即：将 \(000\) 变为 \(0\), 将连续的 \(01\) 或 \(10\) 删掉，我们考虑维护一个栈。
我们从左到右加入每个字符，记当前栈顶为 \(c\)，加入的字符为 \(k\).
- \(c = 0,\ k = 0:\) 若当前栈中有 \(3\) 个 \(0\)，可将它们合并为 \(1\) 个 \(0\).
- \(c = 0,\ k = 1:\) 删去当前的 \(1\) 以及栈顶的 \(0\).
- \(c = 1,\ k = 0:\) 正常加入当前 \(0\).
- \(c = 1,\ k = 1:\) 若栈中 \(1\) 的个数 \(\ge 2\), 可忽略当前新加入的 \(1\)
则维护后的栈必定满足两个性质：
- \(0, 1\) 的个数不超过 \(2\).
- 必定是若干个 \(1\) 接着若干个 \(0\)
回到原题，我们设计动态规划状态为 \(f_{i, j, k}\) 表示做到第 \(i\) 位，当前栈中有 \(j\) 个 \(1\), 有 \(k\) 个 \(0\) 的方案数，按照上面的过程转移即可。
最后答案即使 \(f_{n, 2, 0} + f_{n, 2, 1} + f_{n, 2, 2} + f_{n, 1, 0}.\)
\(\large\mathcal{Code}\)
#include <bits/stdc++.h>
#define reg register
using namespace std;
typedef long long LL;
const int N = 300010, p = 1000000007;
int n;
char ch[N];
LL f[N][3][3];
int main()
{
scanf("%s", ch + 1); n = strlen(ch + 1);
f[0][0][0] = 1;
for (reg int i = 0; i < n; ++ i)
for (reg int j = 0; j < 3; ++ j)
for (reg int k = 0; k < 3; ++ k)
{
if (ch[i + 1] != ‘0‘)
{
if (k) f[i + 1][j][k - 1] = (f[i + 1][j][k - 1] + f[i][j][k]) % p;
else f[i + 1][min(j + 1, 2)][k] = (f[i + 1][min(j + 1, 2)][k] + f[i][j][k]) % p;
}
if (ch[i + 1] != ‘1‘)
{
if (k == 2) f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][k]) % p;
else f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % p;
}
}
printf("%d\n", (f[n][2][0] + f[n][2][1] + f[n][2][2] + f[n][1][0]) % p);
return 0;
}