F. Witnessing the Miracle / 见证奇迹
动态规划。
打表发现当一个被拿走的磁铁集合确定之后，未被拿走的磁铁的方向和距离可以由它左边被拿走的磁铁数量确定，因此，拿走磁铁的先后顺序不影响最终局面的状态，即从 \(S\) 中拿走不同集合的磁铁所对应的状态也是不同的。
考虑从左往右 \(dp\)，设 \(dp_{i,j}\) 表示为 \(S\) 中确定了前 \(i\) 个和 \(T\) 中前 \(j\) 个位置的方案数。
由于磁铁可以往左往右溢出，此时溢出的位置也是合法的，可以将 \(T\) 前后扩 \(n\) 个 \(0\)。
因为可以从右边拿走磁铁使得左边的磁铁左移 \(k\) 位，所以初始化时需初始 \(dp_{0,n-k}\) 为 \(1\)，最终答案也是同理，最右边的可以被右移 \(k\) 位，则答案为 \(dp_{n,2n+k}\)，\(s_{i-1}\) 保留 \(0/1\) 时有转移：
\[dp[i][j] = dp[i][j] + dp[i-1][j-1]\quad \text{ if } s_{i-1} \ne x \land t_{j-1}\ne x，x\in\{0,1\}
\]
\(s_{i-1}\) 为 \(1\) 但不保留时，有转移：
\[dp[i][j] = dp[i][j] + dp[i-1][j-3]\quad \text{ if } t_{j-1}=t_{j-2}=t_{j-3}=0
\]
代码中 Z 类型为取模类。
点击查看代码
using Z = ModInt<MOD[0]>;void solve() {int n, k;std::cin >> n >> k;std::string s, t;std::cin >> s >> t;t = std::string(n, '0') + t + std::string(n, '0');const int lim = 3 * n;std::vector<Z> dp(lim + 1);dp[n - k] = 1;for(int i = 0; i < n; i += 1) {std::vector<Z> ndp(lim + 1);for(int j = 1; j < lim; j += 1) {if(t[j - 1] != '1' && s[i] != '1') {ndp[j] += dp[j - 1];}if(s[i] != '0') {if(t[j - 1] != '0') {ndp[j] += dp[j - 1];}if(j >= 3 && t[j - 1] != '1' && t[j - 2] != '1' && t[j - 3] != '1') {ndp[j] += dp[j - 3];}}}dp = std::move(ndp);}std::cout << dp[2 * n + k] << "\n";}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}