AGC022E Median Replace 题解
FLY_lai
·
·
题解
传送门
题意：给定长度为奇数的 01? 串，问多少种填法使得串可以变成 1。一次操作定义为把连续三个数变成它们的中位数。
这种计数题可以先考虑怎么判定一个串是否可以变成 1，称作合法。
根据人类智慧，可以想到 000S 合法 \iff 0S 合法，进而启示我们考虑串 S 的前几位，看它与什么串的答案等价。
观察发现：
-
-
-
-
-
-
-
第七条是非常显然的，只需证明前六条；而前六条性质从右到左同样非常显然，只需证明前六条的 \Rightarrow 方向。
引理：1S 合法 \iff S 可以变成 01/10/11。
证明：\Leftarrow 显然，只证明 \Rightarrow。
考虑 1S 要变成 1，最后三个数来自 1S 的哪些部分。
-
-
否则 $1S_1$ 对应变成 $1$，根据归纳法，$S_1$ 能变成 $01/10/11$，可以发现无论 $(S_2,S_3)=(1,0)/(0,1)/(1,1)$，$S$ 也都能变成 $01/10/11$。
引理证毕，下面开始证明。
-
- $0+1+S$，这表示因为 $0,1,\text{S 变成的数}$ 要能变成 $1$，所以 $S$ 可以变成 $1$。
- $0+1S_1+S_2$，因为有一个 $0$，所以 $1S_1,S_2$ 都要能变成 $1$。根据引理，$S_1$ 能变成 $01/10/11$，所以 $S_1S_2$ 一起能变出两个 $1$ 一个 $0$，$S$ 合法。
- $01S_1+S_2+S_3$。如果 $01S_1$ 变成的是 $0$，则 $S_2,S_3$ 都变成 $1$，$S=S_1S_2S_3$ 可以变成 $\cdots 11$，$S$ 合法。
否则 $01S_1$ 归纳法证明。
上面六条都可以类似证明，可自行练习。
另外这里可以偷个懒：000S 合法 \Rightarrow 001S 合法 \iff 0S 合法。
在证明了上面六条之后，我们可以建立一个这样的自动机：接受的信号类型只有 0,1 两种。一共七个状态，每个状态对应一个 01 串。每个状态接受信号的目的地，就根据上面的定理。
例如 0 接受了信号 1 就回到代表 "空" 的结点，因为 01S\iff S。
例如 00 接受了信号 0/1 就回到代表 "0" 的结点，因为 000S/001S\iff 0S。
另外，代表 "11" 的结点是终止状态。
于是我们可以在自动机上 DP。dp[i][j] 表示填了前 i 个字符，位于自动机上结点 j 的方案总数。把 id(x) 记为 x 对应的自动机结点编号。注意转移的时候不能从 dp[i][id(11)] 出发转移。
$dp[len][id(1)]$ 很好理解，填完全部之后如果你的串合法等价于 $1$ 合法，当然就合法；后面那一串是因为你的串等价于 $11\cdots$ 时，是一定合法的，只需要统计 $\cdots$ 里面有多少个问号，乘一个二的幂就行了。
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5, MOD = 1e9 + 7;
string s;
ll dp[N][8] = {{}};
int e[10][2];
ll ans = 0;
int main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
cin >> s;
if (s.size() == 1) {
if (s == "1" || s == "?")
cout << 1 << endl;
else
cout << 0 << endl;
return 0;
}
e[1][0] = 2;
e[1][1] = 4;
e[2][1] = 1;
e[2][0] = 3;
e[3][0] = e[3][1] = 2;
e[4][0] = 5;
e[4][1] = 7;
e[5][0] = 6;
e[5][1] = 4;
e[6][0] = e[6][1] = 5;
dp[0][1] = 1;
for (int i = 0; i < s.size(); i++) {
for (int j = 1; j <= 6; j++) {
if (s[i] != '0')
dp[i + 1][e[j][1]] = (dp[i + 1][e[j][1]] + dp[i][j]) % MOD;
if (s[i] != '1')
dp[i + 1][e[j][0]] = (dp[i + 1][e[j][0]] + dp[i][j]) % MOD;
}
}
ans = dp[s.size()][4];
for (ll i = s.size() - 1, pw = 1; i >= 0; i--) {
ans = (ans + dp[i + 1][7] * pw % MOD) % MOD;
if (s[i] == '?')
pw = pw * 2 % MOD;
}
cout << ans << endl;
return 0;
}
```