题目大意
你有一个长度为$n$的串$\texttt{S}$，其中有一些位置上的字符是?，其他的字符则是$0/1$之间的一种
每次可以进行一步操作：选择$3$个连续的字符，并把它们用它们的中位数替换
求有多少种把?替换成$0/1$的方案使得在进行$\frac{n-1}{2}$次操作后剩下的字符为$1$？
分析
我们先考虑如果给定一个符合条件的串，要怎么判定这个串是否合法。
我们维护一个栈，这个栈从栈底到栈顶由一段连续的$1$和一段连续的$0$组成
对于新的一个字符$\texttt{c}$，我们分$0/1$情况考虑
$c=0$，我们发现连续的$3$个$0$可以被抵消成为$1$个$0$，所以如果原来栈顶有$2$个连续的$0$，那么就把这$3$个$0$抵消掉$2$个变成$1$个$0$，否则直接把这个$0$插入栈顶
$c=1$，如果栈顶是$0$，则可以将这个$0$与$1$抵消（因为再找一个数，$3$个数取中位数的话，结果只与新找的数有关），否则把这个$1$插入栈。（如果栈中已经有了两个$1$，则怎么合并剩下的都是$1$，所以如果栈中已经有了两个$1$就可以忽略新的这个$1$了）
然后我们发现栈中$1$的个数只有$0\sim2$这$3$种情况，$0$的个数也只有$0\sim2$这$3$种情况，所以栈的种类数只有$3 \times 3 = 9$种
现在我们考虑怎么$\texttt{dp}$：我们可以把当前栈的状态当做$\texttt{dp}$的状态，设$f[i][j][k]$表示当前处理第$i$位，栈中有$j$个$1$和$k$个$0$，则我们就可以按照上述的方式转移，对于?只要当做$0/1$分别转移一次就可以了。（具体转移可参见代码）
时间复杂度$\mathcal{O(n)}$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
const int mod = 1e9 + 7;
const int MaxN = 3e5 + 10;
char s[MaxN];
ll n, f[MaxN][3][3];
void add(ll &a, ll b) {a += b, ((a > mod) ? (a -= mod) : 0); }
int main()
{
f[0][0][0] = 1;
scanf("%s", s + 1), n = strlen(s + 1);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 3; k++)
{
if(s[i + 1] != '0')
{
if(k)
add(f[i + 1][j][k - 1], f[i][j][k]);
else add(f[i + 1][std::min(j + 1, 2)][k], f[i][j][k]);
}
if(s[i + 1] != '1')
{
if(k == 2)
add(f[i + 1][j][1], f[i][j][k]);
else add(f[i + 1][j][k + 1], f[i][j][k]);
}
}
}
}
ll ans = 0;
for(int i = 0; i < 3; i++)
for(int j = 0; j <= i; j++)
add(ans, f[n][i][j]);
printf("%lld\n", ans);
return 0;
}
|