dp[i][j]:还有i个不相同的位置，还能走j步，一共有多少种走法。
很明显
dp[i][j]=sigm(dp[i-k][j-1]*c[i][k]*c[n-i][m-k]);
用记忆化搜索记忆一下即可。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
using namespace std;
#define maxn 110
#define LL long long
#define mod 1000000009
LL dp[maxn][maxn];
LL c[maxn][maxn];
void init()
{c[0][0]=1;c[1][0]=1;c[1][1]=1;for(int i=2;i<maxn;i++){c[i][0]=1;for(int j=1;j<=i;j++){c[i][j]=c[i-1][j-1]+c[i-1][j];c[i][j]=c[i][j]%mod;}}
}
int n,m,k;
LL dfs(int s,int t,int p)
{// cout<<s<<" "<<t<<" "<<p<<endl;if(dp[s][p]!=-1)return dp[s][p];if(p==0){dp[s][p]=(s==0);// printf("dp[%d][%d]===%lld\n",s,p,dp[s][p]);return dp[s][p];}dp[s][p]=0;for(int i=0;i<=k;i++){if(s<i)continue;if(t<k-i)continue;dp[s][p]+=(c[s][i]*c[t][k-i])%mod*dfs(s-i+(k-i),t+i-(k-i),p-1)%mod;dp[s][p]=dp[s][p]%mod;}
// printf("dp[%d][%d]=%lld\n",s,p,dp[s][p]);return dp[s][p];
}
int main()
{char str[110];char str2[110];init();while(~scanf("%d%d%d",&n,&m,&k)){memset(dp,-1,sizeof(dp));scanf("%s",str);scanf("%s",str2);int s=0;for(int i=0;i<n;i++){if(str[i]!=str2[i])s++;}printf("%lld\n",dfs(s,n-s,m));}return 0;
}