[题解] Flipping Game

题目描述
有n盏灯，每个灯有开和关两种状态。每按一次灯会变成相反的状态。
给定灯初始的开关状态和结束的开关状态，若操作k轮，每轮要按m个不同的灯，问有多少种方法使灯由初始状态变到结束状态。

题解
需注意每轮要按不同的灯，若无这个条件，暴力计算组合数即可。

要操作多轮，且每轮按灯的操作顺序不予考虑。
则可将第i轮视为状态，操作视为状态转移。考虑dp。
设计的状态既需要考虑轮次又需要考虑到是否到达结束状态。

先将问题抽象化：将初始状态和结束状态灯相对比，若状态不同，则灯需按奇数次；否则需按偶数次。
设f[i][j]表示在第i轮，尚有j个灯需按奇数次。
则初始状态f[0][d]=1，f[k][0]为答案。（设d为初始状态和结束状态不同的灯的数量）

转移时考虑：该轮将x个需按奇数次的灯按一次，再按m-x个另外的灯。
f[i][j-x+m-x]=sum(f[i-1][j]/timesC(j,x)*C(n-j,m-x),0<=x<=min(j,m)

代码

#include<bits/stdc++.h> 
#define  int  long long
using namespace std;
const int mod=998244353;
int C[1010][1010];
int f[1010][1010];
void calc(){
	for (int i=0;i<=1007;i++) {
        C[i][0]=1;
        for (int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
}
signed main(){
	int t;
	cin>>t;
	calc();
	while(t--){
		int n,kk,m;
		cin>>n>>kk>>m;
		string s,t;
		cin>>s;
		cin>>t;
		int d=0;
		for(int i=0;i<n;i++)if(s[i]!=t[i])d++;
		f[0][d]=1;
		for(int i=1;i<=kk;i++){
			for(int j=0;j<=n;j++){
				for(int k=0;k<=min(j,m);k++){
					if(n-j<m-k)continue;
					(f[i][j-k+m-k]+=f[i-1][j]*C[j][k]%mod*C[n-j][m-k]%mod)%=mod;
				}
			}
		}
		cout<<f[kk][0]<<"\n";
		for(int i=0;i<=kk;i++)
			for(int j=0;j<=n+m;j++)
				f[i][j]=0;
	}
}