第二次碰到这种东西还是没做出来 /fn。写篇题解加深记忆。
看到这种”相邻区域变色“的问题，要想到黑白染色，然后对黑色区域取反，这样原操作就变成了交换操作。
具体到这道题，就是将奇数位反转，这样就变成了将 换为 。新序列中的 在原序列中是 或
，不能进行操作，而在新序列中，进行操作也无意义，所以就自然地将原题中的操作变为了交换操作。
（之前想过考察奇偶位置，但不知道能怎么办，就没想出来）
然后问题其实就简单了。设
的前缀和为 ， 的前缀和为 ，那么从 变到 的代价就是 。因为最后肯定是 中的第 个 配上 中的第 个 。 就表示有几对
的配对路径经过 这个点。
设 表示 DP 了 中元素 ， 中元素和减 中元素和为 的概率。 表示 DP 了 中元素， 中元素和减 中元素和为 的概率。算答案时枚举 和 ，贡献为 。
于是本题就做完了，时间复杂度为 。
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
46
47
| #include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n;
char s1[N],s2[N];
int f1[N][N + N],f2[N][N + N];
inline void work() {
cin >> n;
cin >> (s1 + 1) >> (s2 + 1);
for(int i = 1;i <= n + 1;i++)
for(int j = -n + N;j <= n + N;j++)
f1[i][j] = f2[i][j] = 0;
for(int i = 1;i <= n;i += 2) {
if(s1[i] != '?') s1[i] ^= 1;
if(s2[i] != '?') s2[i] ^= 1;
}
f1[0][N] = 1;
for(int i = 0;i < n;i++)
for(int j = -i + N;j <= i + N;j++)
for(int c1 = 0;c1 < 2;c1++)
for(int c2 = 0;c2 < 2;c2++) {
if(s1[i+1] != '?' && (c1 ^ (s1[i+1] - '0'))) continue;
if(s2[i+1] != '?' && (c2 ^ (s2[i+1] - '0'))) continue;
Plus(f1[i + 1][j + c1 - c2],f1[i][j]);
}
f2[n + 1][N] = 1;
for(int i = n + 1;i >= 2;i--)
for(int j = -(n-i+1) + N;j <= (n-i+1) + N;j++)
for(int c1 = 0;c1 < 2;c1++)
for(int c2 = 0;c2 < 2;c2++) {
if(s1[i-1] != '?' && (c1 ^ (s1[i-1] - '0'))) continue;
if(s2[i-1] != '?' && (c2 ^ (s2[i-1] - '0'))) continue;
Plus(f2[i - 1][j + c1 - c2],f2[i][j]);
}
int ans = 0;
for(int i = 1;i <= n;i++)
for(int j = -n;j <= n;j++)
Plus(ans,1ll * abs(j) * f1[i][j + N] % P * f2[i + 1][-j + N] % P);
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while(T--) work();
return 0;
}
|