首页 > 代码库 > ZOJ 3791 An Easy Game [组合计数]

ZOJ 3791 An Easy Game [组合计数]

2024-07-12 22:14:49   217人阅读

题目地址：

    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.

解题思路：

    典型的组合计数问题。

  1. 首先比较s1和s2，记s1和s2数码不同的位置有n1个，数码相同的位置有n2个。
  2. 计数，如果第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];

  1. 最后结果就是 a[k][0] （因为没有位置数码不同）

源代码：

 

 1 //zoj3791_zzy_2014.07.19_AC_combinatorial counting 2 #include <iostream> 3  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 }


联系
我们