牛客挑战赛 40 C 题题解

简单题。

考虑到有个性质：

若我们已经知道串 $a$ 、 $b$ 长啥样，就可以用这样的方式计算最小交换次数：

$\forall i \in [1, n]$ ，考虑令 $x$ 等于 $a$ 的长度为 $i$ 的前缀中 $1$ 的出现次数减去 $b$ 的长度为 $i$ 的前缀中 $1$ 的出现次数，则跨过这个位置的交换一定至少有 $x$ 步。
将所有位置的最小交换次数加起来，则可得到将 $a$ 变成 $b$ 的最小交换次数。

注意到需要统计答案的部分只和前缀 $1$ 的个数差有关，于是可以数位 $dp$ ：

考虑设 $f_{i,j,0/1/2/3}$ 表示前 $i$ 个位置，此时 $a$ 、 $b$ 两个串 $1$ 的个数差值为 $j$ ，且：

$a$ 、 $b$ 均贴上界
仅有 $a$ 贴上界
$a$ 、 $b$ 均未贴上界且已经比较出大小
$a$ 、 $b$ 均未贴上界且没有比较出大小

时，所有合法状态的最小交换次数和。再设辅助数组 $g_{i,j,0/1/2/3}$ 表示如上状态的方案数。

然后直接大力讨论转移就行了。

/********************************************************************************

    Code by a weak man who named CYJian, and he hopes the code can get more points.

    Algorithm:

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
    char ch, t = 0; x = 0;
    while(!isdigit(ch = ge)) t |= ch == '-';
    while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
    x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

const int inf = 1e9;
const int mod = 998244353;
const int MAXN = 20010;

inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int &x, int y) { x += y, x -= x >= mod ? mod : 0; }
inline int fsp(int x, int k = mod - 2) {
    int s = 1;
    while(k) {
        if(k & 1) s = 1LL * s * x % mod;
        x = 1LL * x * x % mod, k >>= 1;
    } return s;
}

inline int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }

int f[1010][2010][4];
int g[1010][2010][4];
char s[1010];

int main() {
#ifdef LOCAL
    FILE("a.");
#endif

    scanf("%s", s + 1);
    int n = strlen(s + 1), Ad = 1002;

    g[0][Ad][2] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = -i; j <= i; j++) {
            int G0 = g[i][j + Ad][0];
            int G1 = g[i][j + Ad][1];
            int G2 = g[i][j + Ad][2];
            int G3 = g[i][j + Ad][3];
            int F0 = f[i][j + Ad][0];
            int F1 = f[i][j + Ad][1];
            int F2 = f[i][j + Ad][2];
            int F3 = f[i][j + Ad][3];
/*
            cout << i << ' ' << j << ' ' << 0 << ' ' << G0 << ' ' << F0 << endl;
            cout << i << ' ' << j << ' ' << 1 << ' ' << G1 << ' ' << F1 << endl;
            cout << i << ' ' << j << ' ' << 2 << ' ' << G2 << ' ' << F2 << endl;
            cout << endl;
*/
            Add(g[i + 1][j + Ad][0], Mod(G0 << 1));
            Add(f[i + 1][j + Ad][0], 2LL * (F0 + 1LL * abs(j) * G0) % mod);
            Add(g[i + 1][j + Ad + 1][0], G0);
            Add(f[i + 1][j + Ad + 1][0], (F0 + 1LL * abs(j) * G0) % mod);
            Add(g[i + 1][j + Ad - 1][0], G0);
            Add(f[i + 1][j + Ad - 1][0], (F0 + 1LL * abs(j) * G0) % mod);

            Add(g[i + 1][j + Ad][3], Mod(G3 << 1));
            Add(f[i + 1][j + Ad][3], 2LL * (F3 + 1LL * abs(j) * G3) % mod);
            Add(g[i + 1][j + Ad + 1][0], G3);
            Add(f[i + 1][j + Ad + 1][0], (F3 + 1LL * abs(j) * G3) % mod);

            if(s[i + 1] == '0') {
                Add(g[i + 1][j + Ad][2], G2);
                Add(f[i + 1][j + Ad][2], (F2 + 1LL * abs(j) * G2) % mod);
                Add(g[i + 1][j + Ad][1], G1);
                Add(f[i + 1][j + Ad][1], (F1 + 1LL * abs(j) * G1) % mod);
                Add(g[i + 1][j - 1 + Ad][1], G1);
                Add(f[i + 1][j - 1 + Ad][1], (F1 + 1LL * abs(j) * G1) % mod);
            } else {
                Add(g[i + 1][j + Ad][2], G2);
                Add(f[i + 1][j + Ad][2], (F2 + 1LL * abs(j) * G2) % mod);
                Add(g[i + 1][j + Ad + 1][1], G2);
                Add(f[i + 1][j + Ad + 1][1], (F2 + 1LL * abs(j) * G2) % mod);
                Add(g[i + 1][j + Ad][3], G2);
                Add(f[i + 1][j + Ad][3], (F2 + 1LL * abs(j) * G2) % mod);

                Add(g[i + 1][j + Ad][1], G1);
                Add(f[i + 1][j + Ad][1], (F1 + 1LL * abs(j) * G1) % mod);
                Add(g[i + 1][j + Ad + 1][1], G1);
                Add(f[i + 1][j + Ad + 1][1], (F1 + 1LL * abs(j) * G1) % mod);
                Add(g[i + 1][j + Ad - 1][0], G1);
                Add(f[i + 1][j + Ad - 1][0], (F1 + 1LL * abs(j) * G1) % mod);
                Add(g[i + 1][j + Ad][0], G1);
                Add(f[i + 1][j + Ad][0], (F1 + 1LL * abs(j) * G1) % mod);
            }
        }
    }

    cout << Mod(Mod(f[n][Ad][0] + f[n][Ad][1]) + f[n][Ad][2]) << endl;

    return 0;
}