题解：P14043 [SDCPC 2019] Flipping Game

· · 题解

感觉这题应该是个比较好 dp 的练手题。这篇题解可能是我目前写过各种环境格式一类最复杂的，所以可能会有一些错误。如果发现麻烦指出谢谢。

已使用格式机调整格式。

::::info[说明]{open} 阅读本篇题解的时候请时刻记住翻转“错的”灯会变“对”，翻转“对的”灯会变“错”，并且记住每一个变量。不然可能会效率低下。因为我是这样的。 ::::

因为每一盏灯其实是等价的，所以显然我们并不需要关心具体哪盏灯是亮的，只需要关心当前状态和目标状态相比，有多少盏灯是不一致的。

先推理一下，假设当前有 i 盏灯是错误的，此时我们在 m 中选择了 j 盏灯去调整了错误的灯。那么下一个时间点，错灯总数 sum 为 i - j + (m - j) = i + m - 2j。即减去 j 盏调对的灯，加上 m - j 盏调错的灯。

那么我们可以定义 dp_{r, i} 表示进行完第 r 轮后，恰好有 i 盏灯是“错的”的方案数。此时记初始状态为 s，目标状态为 t，两者位置差距数量为 dif。则初始状态为 dp_{0, dif} = 1，其余为 0，目标是计算出 dp_{k, 0}。

接下来我们考虑相邻两次操作的转移。

从 i 盏错灯里挑选 j 盏，从 n - i 盏对灯里挑选 m - j 盏。所以方法数 w 是 \binom{i}{j} \times \binom{n-i}{m-j} (\bmod 998244353)。

据此，我们开始推算转移方程。

对于每一轮 r（从 1 到 k）中，对于每一种可能的错灯数量 i（从 0 到 n），如果 dp_{r - 1, i} \ne 0，则枚举 j 的所有合法取值（\max(0, m - (n - i)) \le j \le \min(i, m)）

则有状态转移方程 dp_{r, sum} \gets (dp_{r, sum} + dp_{r - 1, i} \times w) \bmod 998244353。

复杂度是 O(Tknm)。注意到：

保证 n > 20 的时候测试数据不会超过 100 组。

所以运算量大约在 10^8 次左右，能跑过。

::::success[AC code]

/*

time : <DATETIME>

contest :

Problem : 

Solution :

Code by 720872

*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<climits>
#include<bitset>
#define ll long long
#define ull unsigned long long
#define il inline
#define endl '\n'
#define y1 Y1
#define pii pair<int,int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define _1 first
#define _2 second
#define mkp make_pair
#define pb push_back
#define debug cout << "debug" << endl;
#ifdef __unix__
#define gc getchar_unlocked
#else
#define gc _getchar_nolock
#endif
using namespace std;

inline ll read(){
    ll k = 0, f = 1, c = gc();
    for (; !isdigit(c); c = gc()) if (c == '-') f = -1;
    for (; isdigit(c); c = gc()) k = k * 10 + (c ^ 48);
    return k * f;
}
//inline void put(ll x){
//  if(x < 0) putchar('-'), x = -x;
//  if(x < 10) putchar(x + '0');
//  else put(x / 10), putchar(x % 10 + '0');
//}

const int N = 105;
const ll mod = 998244353;
int n, k, m, dif;
char s[N], t[N];
ll dp[N][N];   // dp[r][i]: 第 r 轮后，恰有 i 盏灯是错的方案数
ll C[N][N];    // 组合数

void init(){
    // 预处理组合数 C[n][m]
    for(int i = 0; i < N; i++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
    }
}

void solve(){
    n = read(), k = read(), m = read();
    scanf("%s%s", s + 1, t + 1);
    // 统计初始错误数量
    dif = 0;
    for(int i = 1; i <= n; i++)
        if(s[i] != t[i]) dif++;
    // dp 清零
    memset(dp, 0, sizeof(dp));
    dp[0][dif] = 1;
    for(int r = 1; r <= k; r++){
        for(int i = 0; i <= n; i++){
            if(dp[r-1][i] == 0) continue;
            // 枚举本轮翻转的错误灯数量 j
            int L = max(0, m - (n - i));  // 对灯不够，必须翻错灯
            int R = min(i, m);            // 错灯不够，最多翻 i 盏
            for(int j = L; j <= R; j++){
                int sum = i - j + (m - j);  // 新错灯数 = 旧错灯 - 修对的 + 新增修错的
                ll w = C[i][j] * C[n - i][m - j] % mod;
                dp[r][sum] = (dp[r][sum] + dp[r-1][i] * w) % mod;
            }
        }
    }
    cout << dp[k][0] << endl;
}

signed main(){
    init();
    int T = read();
    while(T--) solve();
    return 0;
}

::::