飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5299

题意：给你n，k，m和两个长度为n的只包含'0'和'1'的字符串，给你k步，每步要正好改变s1字符串m个位置,使得k步后s1和s2相等，问总共有多少中方法，取模输出。

分析：这种题一看，以为是按字符串DP，其实发现如果按字符串DP 那复杂度就太大了我们发现字符串就只有0，1，所以可以按状态来DP，具体DP 的话，假设当前为第i步，我们需要去m个位置，具体m个位置我们可以，不一样的位置取j个，那么一样的位置就是m-j个，然后从i-1进行迭代。如果i-1存在不同位置有x个，相同位置 为n-x个，如果x>=j&&n-x>=m-j，且这个方法是可以行的通的，i-1时的方法数为ans,那么我们就可以从x里面取j个，n-x取m-j个，这里的话是组合所以我们可以预处理出C[100][100]，最后答案怎么算呢？仔细想想就会有思路，因为x里去了j个，所以剩下不一样的位置为x-j个，但是一样的位置里面取了,m-j个，最后剩下的不一样的位置 有x-j+m-j个同理，一样的位置有n-x-(m-j)+j个，假设为j为js，m-j为os,x为js1，n-x为os1，且更新后的为x-j+m-j为njs，n-x-(m-j)+j为nos,则状态方程为 ai[i][njs][nos]+=ai[i-1][js1][os1]*C[js1][js]*C[os1][os];记得取模，复杂度为n^3,最后啪啪啪就可以AC了

/*
Author:Chieh
Grow up happy
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#define LL long long
using namespace std;
const int MOD=1000000009;
const int maxn=123;
LL ai[maxn][maxn][maxn];
LL C[maxn][maxn];
char ch1[maxn],ch2[maxn];
int n,k,m;
void init()
{
    int diff=0;
    scanf("%s%s",ch1+1,ch2+1);
    int len=strlen(ch1+1);
    for(int i=1; i<=len; i++)
    {
        if(ch1[i]!=ch2[i])diff++;
    }
    memset(ai,0,sizeof(ai));
    ai[0][diff][len-diff]=1;
}
void play()
{

    for(int i=1; i<=k; i++)
    {
        for(int j=0; j<=m; j++)
        {
            int js=j;
            int os=m-j;
            for(int l=js; l<=100; l++)
            {
                int js1=l;
                int os1=n-l;
                if(os1<0)break;
                if(js1>=js&&os1>=os&&ai[i-1][js1][os1]>0)
                {
                    int njs=js1-js;
                    njs+=os;
                    int nos=os1-os;
                    nos+=js;
                    ai[i][njs][nos]+=((ai[i-1][js1][os1]*C[js1][js]%MOD)*C[os1][os]%MOD);
                    ai[i][njs][nos]%=MOD;
                }

            }
        }
    }
    printf("%lld\n",ai[k][0][n]);
}
int main()
{
    C[0][0]=1;
    for(int i=0; i<=100; 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;
        }
    }

    while(scanf("%d%d%d",&n,&k,&m)!=EOF)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}