Flipping Game ZOJ - 4114 | dp + 组合数

去年省赛题现在才AC。
我早应该补的，这道题我学到了好多知识点，值了。
省赛的时候看了两个小时没看出来是dp，就算看出来了也ac不了，太菜了。。

题意：
给你n个开关，一共是kk轮，一轮可以关m个灯（这m个灯必须都不同），问你有多少种方法能从初始状态到达最终状态。
分析：

• dp[i][j]表示到第i轮的时候，有j个灯是合法的情况数。
• 转移其实不难想，主要是枚举的对象，如果枚举的是第i轮的合法数，则子问题不好确定，if判断条件也不好写（至少我没想出来。。）;相反，如果枚举的是i-1轮的合法数，那么不但p的范围好确定，p确定之后该子问题的转移方向也就很清晰了（该状态可以向多个方向转移）
• 逆元的表要先打出来，不然会tle，因为每次求逆元会把复杂度提高一个数量级（顺带复习了一波大组合数求法）
  代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 998244353;
const int maxn = 1e2 + 10;
const int inf = 0x3f3f3f3f;
ll fac[maxn];
ll inv[maxn];
ll dp[maxn][maxn];
int v1[maxn], v2[maxn];

ll powmod(ll a, ll n)
{
    ll res = 1;
    while(n)
    {
        if(n & 1) res = res * a % mod;
        n >>= 1;
        a = a * a % mod;
    }
    return res;
}

void init()
{
    fac[0] = 1;
    for(int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % mod, inv[i] = powmod(fac[i], mod - 2);
}

ll c(ll n, ll m)
{
    if(m == 0 || m == n) return 1; 
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
    int t; cin >> t;
    init();
    while(t--)
    {
        mem(dp, 0);
        int n, k, m; scanf("%d%d%d", &n, &k, &m);
        int cnt = 0;
        for(int i = 1; i <= n; i++) scanf("%1d", v1 + i);
        for(int i = 1; i <= n; i++) scanf("%1d", v2 + i), cnt += v1[i] == v2[i];
        dp[0][cnt] = 1;
        for(int i = 1; i <= k; i++)
            for(int j = 0; j <= n; j++)
                for(int p = 0; p <= m; p++)
                {
                    if(p <= j && m - p <= n - j)
                    {
                        dp[i][j - p + m - p] += dp[i - 1][j] * c(j, p) % mod * c(n - j, m - p) % mod;
                        dp[i][j - p + m - p] %= mod;
                    }
                }
        printf("%lld\n", dp[k][n]);
    }
}