CF1615F LEGOndary Grandmaster 题解

· · 题解

这题于看似简单的思路与代码中，蕴含着好几个美妙的技巧。下面就由我来一一解说。如果理解了这些小技巧，不仅能轻松理解这题思路，还能在做到类似题目时触类旁通，举一反三。

技巧一：操作的转化

原题中的取反操作要求两个连续的数都相同，那么我们可以将奇数位上的数取反，然后转化为交换操作。交换操作有一个特点，就是可以保证交换的两个数不相等，对应原字符串中就是两个数相等，这样很巧妙的满足了这个条件。

技巧二：次数的计算

首先，很明显推到这里，少了一个限制，这种题目的计算公式已经不会很复杂了。设 x 数组中存了第一个串中 1 出现的下标，y 数组中存了第二个串中 1 出现的下标，那么次数就是 \sum |x_i-y_i|。但这样计算起来就不是很方便。接下来可以利用一个套路的结论。设 a_i 表示第一个串中前 i 个数 1 的个数，b_i 表示第二个串中前 i 个数 1 的个数，次数就是 \sum |a_i-b_i|。因为你每交换两个数，最多只能使一个前缀和发生变化。

技巧三：利用贡献法。

讲到这里，我想最后一步也十分简单了。对于每个 i，我们枚举 j = a_i-b_i，计算这个 j 的贡献。具体的，可以令 pre_{i, j} 表示前 i 个数使 a_i - b_i = j 的方案数， suf_{i, j} 则表示相应的后缀的方案，那么 (i,j) 的贡献就是 pre_{i, j} \times suf_{i+1,-j} \times |j|。并且经过转化之后，这个转移也变得十分简单。

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, N = 2005;
typedef long long LL;
int n;
LL suf[N][N << 1], pre[N][N << 1];
char a[N], b[N];
bool equal(char a, int b) {
    return a == '?' || a == b + 48;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%s%s", &n, a + 1, b + 1);
        for (int i = 0; i <= n + 1; ++i)
            for (int j = 0; j <= 2 * n; ++j)
                suf[i][j] = pre[i][j] = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i] != '?' && (i & 1)) a[i] = (a[i] ^ 48 ^ 1) + 48;
        for (int i = 1; i <= n; ++i)
            if (b[i] != '?' && (i & 1)) b[i] = (b[i] ^ 48 ^ 1) + 48;
        pre[0][n] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j <= 2 * n; ++j)
                for (int k = 0; k <= 1; ++k)
                    for (int p = 0; p <= 1; ++p) 
                        if (equal(a[i + 1], k) && equal(b[i + 1], p) && j + k - p >= 0) (pre[i + 1][j + k - p] += pre[i][j]) %= P;
        suf[n + 1][n] = 1;
        for (int i = n + 1; i >= 2; --i)
            for (int j = 0; j <= 2 * n; ++j)
                for (int k = 0; k <= 1; ++k)
                    for (int p = 0; p <= 1; ++p) 
                        if (equal(a[i - 1], k) && equal(b[i - 1], p) && j + k - p >= 0) (suf[i - 1][j + k - p] += suf[i][j]) %= P;
        LL ans = 0;
        for (int i = 1; i < n; ++i)
            for (int j = -n; j <= n; ++j)
                (ans += pre[i][j + n] * suf[i + 1][n - j] % P * abs(j) % P) %= P;
        printf("%lld\n", ans);
    }
}