概率水题，或者可以用搜索。题意：给你n个1和m个0，它们能组成q种不同的排列组合字符串，记p为这些字符串中出现01子串的次数，输出p/q的最简形式。
我的解题思路：用求概率的思路来推的话结果是(n×m)/(n+m)的最简分数形式，，可是我不会。由于数据规模不大，所以也可以用dfs搜索来求出答案，dfs记录上一个数字，剩余1和0的个数还有已出现01串的次数就好了。
我的解题代码：
#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <queue>#include <cmath>#include <climits>#include <algorithm>#include <vector>#include <map>using namespace std;typedef long long Long;Long p, q;Long ansp, ansq;Long Gcd(Long a, Long b){return b == 0 ? a : Gcd(b, a % b);}void Dfs(int prev, int one, int zeo, int flag){if (one > 0) Dfs(1, one-1, zeo, prev == 0 ? flag + 1 : flag);if (zeo > 0) Dfs(0, one, zeo-1, flag);if (0 == one && 0 == zeo){ansq++;ansp += flag;}return;}int main(){while (~scanf("%lld %lld", &p, &q)){if (p < 1 || q < 1) while (true);ansp = ansq = 0;if (p > 0) Dfs(1, p-1, q, 0);if (q > 0) Dfs(0, p, q-1, 0);Long tmp = Gcd(ansp, ansq);printf("%lld/%lld\n", ansp / tmp, ansq / tmp);}return 0;}
快乐不是因为拥有的多而是计较的少
