给出两个等长的字符串，每次需要改变m个数字，每次必须改变k个数字，求从第一个串变化到第二个串的方案数。
DP。f[i][j]改变i步后，有j个位置被改变的方案数。然后直接枚举当前改变的几个位置是前面重合的。
然后统计答案输出即可。
#include <iostream>
#include <cstring>
#include <cstdio>
#define M 1000000009
#define maxn 105
typedef long long ll;
using namespace std; ll C[maxn][maxn];
ll f[maxn][maxn];
int n,k,m,change;
ll ans; ll power(ll A,ll B)
{
ll tot=;
while (B){
if (B&) tot=tot*A%M;
A=A*A%M,B>>=;
}
return tot;
} void _init()
{
memset(C,,sizeof C);
C[][]=;
for (int i=; i<maxn; i++){
C[i][]=;
for (int j=; j<=i; j++) C[i][j]=(C[i-][j]+C[i-][j-])%M;
}
} int main()
{
_init();
char s1[maxn],s2[maxn];
while (scanf("%d%d%d",&n,&k,&m)!=EOF){
change=;
scanf("%s%s",s1,s2);
for (int i=; i<n; i++)
if (s1[i]!=s2[i]) change++;
memset(f,,sizeof f);
f[][]=;
for (int i=; i<k; i++)//after the ith time of changes
for (int j=; j<=n; j++){//the number of 1 is j
if (f[i][j]==) continue;
for (int x=max(,j+m-n); x<=min(j,m); x++){
f[i+][j-x+m-x]+=f[i][j]*(C[j][x]*C[n-j][m-x]%M)%M;
f[i+][j-x+m-x]%=M;
}
}
ans=f[k][change]*power(C[n][change],M-)%M;
printf("%d\n",(int)ans);
}
return ;
}