题目地址：
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3791
题目描述：
给定两个长度为n的01串s1，s2，要求用k步，每一步反转s1的m个位置的数码（即0变为1，1变为0），问能有多少种做法，在k步之后将s1变成s2。
1 <= n <= 100, 0 <= k <= 100, 0 <= m <= n.
解题思路：
典型的组合计数问题。
- 首先比较s1和s2，记s1和s2数码不同的位置有n1个，数码相同的位置有n2个。
- 计数，如果第k1步结束后，s1和s2有odd个不同的位置，even个相同的位置（odd + even = n）的情况有a[k1][odd]种方法。从odd中取出i个，从even中取出j个进行反转（I + j = m），取法有C[odd][i] * C[even][j]种。不难看出计数方程：
a[k1 + 1][odd – I + j] += a[k1][odd] * C[odd][i] * C[even][j];
- 最后结果就是 a[k][0] （因为没有位置数码不同）
源代码：
1 //zoj3791_zzy_2014.07.19_AC_combinatorial counting 2 #include3 4 using namespace std; 5 6 typedef long long LL; 7 8 class EasyGame 9 {10 public:11 EasyGame(LL N, LL K, LL M): n(N), k(K), m(M) {12 ans = 0;13 ini();14 for(int i = 0; i < 2; ++i)15 for(int j = 0; j <= n; ++j)16 a[i][j] = 0;17 }18 void getString();19 void solve();20 int getAns();21 private:22 static const LL mod = 1000000009;23 LL n, k, m, n1, n2, ans;24 string s1, s2;25 LL C[101][101];26 LL a[2][101];27 void ini();28 };29 30 void EasyGame::ini()31 {32 C[0][0] = 1;33 C[1][0] = 1;34 C[1][1] = 1;35 for(int i = 2; i <= n; ++i) {36 C[i][0] = 1;37 C[i][i] = 1;38 for(int j = 1; j < i; ++j) {39 C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;40 }41 }42 }43 44 void EasyGame::getString()45 {46 cin >> s1;47 cin >> s2;48 n1 = n2 = 0;49 for(int idx = 0; idx < s1.size(); ++idx) {50 if(s1[idx] != s2[idx])51 n1++;52 else53 n2++;54 }55 }56 57 void EasyGame::solve()58 {59 a[0][n1] = 1;60 for(int step = 1; step <= k; ++step) {61 for(int idx = 0; idx <= n; ++idx)62 a[step % 2][idx] = 0;63 for(int odd = 0; odd <= n; ++odd) {64 int even = n - odd;65 for(int i = 0; i <= m; ++i) {66 int j = m - i;67 if(i > odd) break;68 if(j > even) continue;69 int odd2 = odd - i + j;70 a[step % 2][odd2] += a[(step - 1) % 2][odd] * (C[odd][i] * C[even][j] % mod) % mod;71 a[step % 2][odd2] %= mod;72 }73 }74 }75 ans = a[k % 2][0];76 }77 78 int EasyGame::getAns()79 {80 return ans;81 }82 83 int main()84 {85 LL N, K, M;86 while(cin >> N >> K >>M)87 {88 EasyGame *egp = new EasyGame(N, K, M);89 egp -> getString();90 egp -> solve();91 cout << egp -> getAns() << endl;92 }93 return 0;94 }