D. Shift and Flip
给定两个 \(01\) 串 \(A\) 和 \(B\)，每次操作可以将 \(A\) 循环左移或右移一位，或选择一个 \(B_i = 1\) 的位置将 \(A_i\) 取反，求使 \(A\) 和 \(B\) 相等至少要进行几次操作。
\(n \leq 2 \times 10^3\)。
显然，无解当且仅当 \(B\) 中不存在 \(1\)，且 \(A\) 中存在 \(1\)。
结合数据范围，容易想到先枚举最终 \(A\) 和 \(B\) 的对齐方式，这时操作 \(3\) 的次数是固定的，也就是 \(A\) 和 \(B\) 不同的位置个数。现在我们要最小化前两个操作的次数和。
对每个 \(i\)，我们求出 \(p_i\) 表示使得 \(b_{i - j} = 1\) 的 \(j\) 的值，\(q_i\) 表示使得 \(b_{i+j} = 1\) 的 \(j\) 的值（下标运算默认在 \(\text{mod} \ n\) 意义下进行）。利用调整法容易说明如下事实：设 \(L\) 为左移长度，\(R\) 为过原点后右移长度，那么最优方案中 \(A\) 的移动一定是分为两段：向左移动 \(L\)，回到原点，向右移 \(R\)（或者相反），然后和 \(B\) 对齐。并且，\(L\) 一定恰等于某个 \(p_i\)，\(R\) 一定恰等于某个 \(q_i\)。
考虑每次枚举对齐方式后如何求出 \(L,R\)：我们将所有没有匹配上的位置找出来，那么 \(L,R\) 合法当且仅当对于每一个失配点 \(i\) 都有 \(L \geq p_i\) 或 \(R \geq q_i\)。将二元组 \((p_i,q_i)\) 以 \(q_i\) 为关键字从小到大排序，设 \(f_i\) 为 \(p_i\) 的后缀最大值，那么所有可能最优的合法解即为 \(L_i =f_{i+1},R_i = q_i\)，枚举即可。
由于 \(\forall i,q_i < n\)，使用基数排序，时间复杂度 \(O(n^2)\)。
code
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
#define mem(x, v) memset(x, v, sizeof(x))
using namespace std;
const int N = 2e3 + 5, inf = 0x3f3f3f3f;
int n, m, ans, L[N], R[N], buk[N], vr[N], suf[N], tmp[N];
char s[N]; bool a[N], b[N], sa, sb;
int main() {
scanf("%s", s), n = strlen(s);
for (int i = 0; i < n; i++) a[i] = s[i] - '0';
scanf("%s", s);
for (int i = 0; i < n; i++) b[i] = s[i] - '0';
mem(L, inf), mem(R, inf);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (b[j])
L[i] = min(L[i], (i - j + n) % n), R[i] = min(R[i], (j - i + n) % n);
for (int i = 0; i < n; i++) sa |= a[i], sb |= b[i];
if (!sb) return puts(sa ? "-1" : "0"), 0;
ans = inf;
for (int i = 0; i < n; i++) {
m = 0;
for (int j = 0, k = i; j < n; j++, k++, k %= n) if (a[k] != b[j]) vr[++m] = k;
for (int i = 0; i <= n; i++) buk[i] = 0;
for (int i = 1; i <= m; i++) buk[R[vr[i]]]++;
for (int i = 1; i <= n; i++) buk[i] += buk[i - 1];
for (int i = m; i >= 1; i--) tmp[buk[R[vr[i]]]--] = vr[i];
for (int i = 1; i <= m; i++) vr[i] = tmp[i];
suf[m + 1] = 0;
for (int j = m; j >= 1; j--) suf[j] = max(suf[j + 1], L[vr[j]]);
ans = min(ans, max(i, suf[1]) * 2 - i + m);
ans = min(ans, (suf[1] + (n - i) % n) * 2 - (n - i) % n + m);
for (int j = 1; j <= m; j++) {
ans = min(ans, (R[vr[j]] + max(i, suf[j + 1])) * 2 - i + m);
ans = min(ans, (suf[j + 1] + max((n - i) % n, R[vr[j]])) * 2 - (n - i) % n + m);
}
}
cout << ans << endl;
return 0;
}
E. Shuffle and Swap
给定两个长度为 \(n\) 的 \(01\) 串 \(A\) 和 \(B\)，两个串均有 \(k\) 个 \(1\)。
令 \(a_{1\sim k}\) 和 \(b_{1\sim k}\) 分别表示 \(A\) 和 \(B\) 中所有 \(1\) 出现的位置。现将 \(a\) 和 \(b\) 等概率随机排列，按 \(1\sim k\) 的顺序交换 \(A_{a_i}\) 和 \(A_{b_i}\)，求有多少种不同的排列方式使得操作结束后 \(A\) 和 \(B\) 相等。答案对 \(998244353\) 取模。
\(n \leq 10^4\)，时限 \(\text{2.0s}\)。
不妨先分析一下操作的结构：
我们将所有点分成三类：\(A_i = 0\) 且 \(B_i = 1\)，\(A_i = 1\) 且 \(B_i = 0\)，以及 \(A_i = B_i = 1\)。
我们的目标是，将所有 \(1\) 类点的 \(0\) 传出去，其中可能经过一些 \(3\) 类点，然后到达一个 \(2\) 类点。换句话说，我们需要将所有 \(1\) 类点和 \(2\) 类点匹配。
为了更精确地刻画这个过程，我们建立这样一张图：如果操作了 \(a_i,b_i\) 就连边 \(b_i \to a_i\)，那么此时 \(1\) 类点出度为 \(1\)，\(2\) 类点入度为 \(1\)，\(3\) 类点入度和出度均为 \(1\)。也就是说，这张图一定由若干链和环组成，其中链的条数是确定的，也就是 \(1\) 类点的数量。
不妨考虑有多少 \(3\) 类点在链上，我们枚举这个值，设 \(1\) 类点有 \(p\) 个，\(3\) 类点有 \(q\) 个，\(f_{i,j}\) 为有 \(i\) 个 \(3\) 类点，组成 \(j\) 条链的排列数，那么答案即为
\[\sum_{k=0}^q \binom{q}{k} \binom{p+q}{k} \cdot (k!)^2 \cdot f_{p,q-k} \]其组合意义显然，\((k!)^2\) 是因为剩下的 \(3\) 类点可以随便匹配。现在的问题变成了如何求 \(f\)。考虑转移：
-
在序列末尾新建一条链，这需要选择一个 \(1\) 类点和一个 \(2\) 类点，因此 \(f_{i,j} \gets f_{i-1,j} \cdot i^2\)。
-
在某条链的末尾插入一个 \(3\) 类点，这需要选择一条链以及一个 \(3\) 类点，因此 \(f_{i,j} \gets f_{i,j - 1} \cdot i \cdot j\)。
综上可得 \(f_{i,j} = f_{i-1,j} \cdot i^2 + f_{i,j-1} \cdot i \cdot j\)，由于我们每次只在末尾插入，因此不会算重。直接算就行了，时间复杂度 \(O(n^2)\)。
code
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, mod = 998244353;
int qpow(int a, int b = mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return ret;
}
int n, p, q, ans, f[N][N], fac[N], inv[N];
char a[N], b[N];
int main() {
scanf("%s %s", a + 1, b + 1), n = strlen(a + 1);
for (int i = 1; i <= n; i++) p += (a[i] == '1' && b[i] == '0'), q += (a[i] == '1' && b[i] == '1');
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[n] = qpow(fac[n]);
for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % mod;
for (int i = 0; i <= p; i++) f[i][0] = 1ll * fac[i] * fac[i] % mod;
for (int i = 1; i <= p; i++)
for (int j = 1; j <= q; j++)
f[i][j] = 1ll * (1ll * f[i - 1][j] * i % mod + 1ll * f[i][j - 1] * j % mod) % mod * i % mod;
for (int i = 0; i <= q; i++)
ans = (ans + 1ll * fac[q] * fac[p + q] % mod * ifac[q - i] % mod * ifac[p + q - i] % mod * f[p][q - i] % mod) % mod;
cout << ans << endl;
return 0;
}
F. Yes or No
有 \(n+m\) 个问题，其中有 \(n\) 个问题的答案是 Yes，\(m\) 个问题的答案是 No。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。答案对 \(998244353\) 取模。
\(n,m \leq 10^5\)。
感性理解一下，我们的最优策略是：假设此时已知 Yes 有 \(n\) 个而 No 有 \(m\) 个，若 \(n > m\) 则回答 Yes，若 \(n < m\) 回答 No，否则回答 Yes 或 No 均可。
把这个问题放到数轴上考虑，点 \((n,m)\) 表示当前 Yes 有 \(n\) 个而 No 有 \(m\) 个，那么一道题答案为 Yes 相当于往左走一步，答案为 No 相当于往下走一步。那么我们回答的过程相当于是一条 \((n,m) \to (0,0)\) 的路径。
我们画一条直线 \(y=x\)，如果不考虑直线上的点，那么答案显然是 \(\max(n,m)\)。考虑这条直线对答案的影响：位于 \(y=x\) 上的点表示剩下的问题中，答案为 Yes 和 No 的一样多，这时我们猜对的概率为 \(\frac{1}{2}\)。于是只需要计算每个 \(y=x\) 上的点被经过多少次即可算出直线的额外贡献。
经过点 \((i,i)\) 的方案数为 \(\binom{2i}{i} \times \binom{n+m -2\times i}{n-i}\)，而总路径数为 \(\binom{n+m}{m}\)，所以一个点 \((i,i)\) 的贡献就是 \(\dfrac{1}{2} \times \dfrac{\binom{2i}{i} \times \binom{n+m -2\times i}{n-i}}{\binom{n+m}{m}}\)。据此容易计算总贡献，时间复杂度 \(O(n)\)。
code
/*
挥拂去蒙尘半生的晦暗
用这嶙峋双臂迎接 振翅吧 我的蝴蝶
最后一支 赤诚赞歌盘旋
潮起潮落翻覆昼夜 澎湃在生命刻度之前
此刻色彩挣脱谎言 献予你 赤红纸花遍野
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 998244353;
int qpow(int a, int b = mod - 2, int ret = 1) {
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return ret;
}
int n, m, fac[N], inv[N];
void add(int &x, int y) { x = (x + y >= mod) ? (x + y - mod) : (x + y); }
int C(int n, int m) {
return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
ios :: sync_with_stdio(0);
cin >> n >> m; int L = 2 * max(n, m);
fac[0] = inv[0] = 1;
for (int i = 1; i <= L; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[L] = qpow(fac[L]);
for (int i = L; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % mod;
int ans = 0;
for (int i = 1; i <= min(n, m); i++) add(ans, 1ll * C(2 * i, i) * C(n - i + m - i, n - i) % mod);
ans = 1ll * ans * inv[2] % mod * inv[n + m] % mod * fac[n] % mod * fac[m] % mod;
add(ans, max(n, m));
cout << ans << endl;
return 0;
}