2014百度之星复赛解题报告：The Game of Coins

The Game of Coins

时间限制：10s  内存限制：64MB

问题描述

Cirno和Marisa经常在一起玩抛硬币的游戏，每次由Cirno先选择正面(H)或反面(T)，然后抛一次硬币，如果结果和Cirno的选择一致，则Cirno赢，如果结果相反，则Marisa赢。有一天，Marisa对Cirno说，过去的玩法都弱爆了，给Cirno介绍了一种新的玩法。现在Cirno每次选择一个长度为n的由H和T组成的字符串，然后Marisa也选择一个不同的字符串，随后她们不断抛硬币，直到其中一个人选择的字符串和最后n次抛硬币的结果相匹配，匹配的人将获胜。玩了一段时间后，Cirno发现自己的胜率下降了，但又不知道为什么。现在，Cirno想知道在给定自己和Marisa所选的字符串时，自己获胜的概率。

输入

第一行为T，表示输入数据组数。

下面T组数据。每组数据都是两个空格分割的，长度均为n的，由H和T组成的字符串。

输出

对第i组数据，输出

Case #i:

然后输出Cirno获胜的概率，并以最简分数形式输出。

限制条件

1<=T<=500

1<=n<=9+9+9

样例输入

3

H T

HT TH

HH TH

样例输出

Case #1:

1/2

Case #2:

1/2

Case #3:

1/4

解题报告：
# input1/output1: n <=3
方法比较多，可以用和input2/outpu2类似的方法，以2^n为状态。
也可以用Monte Carlo求出浮点数解，反过来得到精确解（可以假设分母都不会太大）。
还可以利用对称性分类，再人肉求解后打表（有不少是1/2）。

# input2/output2: n <= 27
以输入的字符串a和b的所有后缀作为状态，每抛一次硬币，就有一半的概率转移到两个新的状态。
状态a和b本身是终止状态，对应的胜率分别为1和2。
p_a = 1
p_b = 0
而对于其余状态i，则有
p_i = 0.5 * p_{s(i+H)} + 0.5 * p_{s(i+T)}
于是可以得到一个n元线性方程组，用Gauss消元法可解。

# input3/output3: n <= 729
算法参考solution3.rb。
记k_{ij}=correlation(i, j), k_i=k_{ii}-k_{ij}
a胜利的概率是k_b/(k_a+k_b)
b胜利的概率是k_a/(k_a+k_b)

参考：String overlaps, pattern matching, and nontransitive games。

解题代码：

#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long llint;

llint gcd(llint a, llint b) {
  return b == 0 ? a : gcd(b, a % b);
}

struct Fraction {
  llint num, den;

  Fraction(llint n = 0, llint d = 1): num(n), den(d) {
    llint g = gcd(num, den);
    num /= g;
    den /= g;
    if (den < 0) {
      num = -num;
      den = -den;
    }
  }
};

Fraction operator+(const Fraction& lhs, const Fraction& rhs) {
  llint g = gcd(lhs.den, rhs.den);
  return Fraction(lhs.num * (rhs.den / g) + rhs.num * (lhs.den / g), lhs.den / g * rhs.den);
}

Fraction operator-(const Fraction& lhs, const Fraction& rhs) {
  return lhs + Fraction(-rhs.num, rhs.den);
}

Fraction operator*(const Fraction& lhs, const Fraction& rhs) {
  llint g1 = gcd(lhs.num, rhs.den);
  llint g2 = gcd(rhs.num, lhs.den);
  return Fraction((lhs.num / g1) * (rhs.num / g2), (lhs.den / g2) * (rhs.den / g1));
}

Fraction operator/(const Fraction& lhs, const Fraction& rhs) {
  return lhs * Fraction(rhs.den, rhs.num);
}

Fraction operator==(const Fraction& lhs, const Fraction& rhs) {
  return lhs.num == rhs.num && lhs.den == rhs.den;
}


const int MAXN = 64;

void LU(int n, Fraction a[MAXN][MAXN], int r[MAXN], int c[MAXN]) {
  for (int i = 0; i < n; ++i) {
    r[i] = c[i] = i;
  }
  for (int k = 0; k < n; ++k) {
    int ii = -1, jj = -1;
    for (int i = k; ii == -1 && i < n; ++i) {
      for (int j = k; jj == -1 && j < n; ++j) {
        if (a[i][j].num != 0) {
          ii = i;
          jj = j;
        }
      }
    }
    swap(r[k], r[ii]);
    swap(c[k], c[jj]);
    for (int i = 0; i < n; ++i) {
      swap(a[i][k], a[i][jj]);
    }
    for (int j = 0; j < n; ++j) {
      swap(a[k][j], a[ii][j]);
    }
    for (int i = k + 1; i < n; ++i) {
      a[i][k] = a[i][k] / a[k][k];
      for (int j = k + 1; j < n; ++j) {
        a[i][j] = a[i][j] - a[i][k] * a[k][j];
      }
    }
  }
}

void solve(int n, Fraction a[MAXN][MAXN], int r[MAXN], int c[MAXN], Fraction b[MAXN]) {
  static Fraction x[MAXN];
  for (int i = 0; i < n; ++i) {
    x[i] = b[r[i]];
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      x[i] = x[i] - a[i][j] * x[j];
    }
  }
  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j > i; --j) {
      x[i] = x[i] - a[i][j] * x[j];
    }
    x[i] = x[i] / a[i][i];
  }
  for (int i = 0; i < n; ++i) {
    b[c[i]] = x[i];
  }
}

Fraction a[MAXN][MAXN];
int r[MAXN];
int c[MAXN];
Fraction b[MAXN];

int main() {
  int n, m;
  string x, y, z;
  vector<string> v;

  int TT, NN;
  cin >> NN;
  for (TT = 1; TT <= NN; TT++) {
    cin >> x >> y;
    v.clear();
    n = x.length();
    for (int i = 0; i <= n; ++i) {
      v.push_back(x.substr(0, i));
      v.push_back(y.substr(0, i));
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m = v.size();

    for (int i = 0; i < m; ++i) {
      fill(a[i], a[i] + m, 0);
      a[i][i] = 1;
      b[i] = v[i] == x ? 1 : 0;
      if (v[i] == x || v[i] == y) {
        continue;
      }
      const char char_list[2] = {'H', 'T'};
      for (int list_idx = 0; list_idx < 2; list_idx ++) {
        char c = char_list[list_idx];
        //for (char c: {'H', 'T'}) {
        z = v[i] + c;
        while (find(v.begin(), v.end(), z) == v.end()) {
          z = z.substr(1);
        }
        int j = find(v.begin(), v.end(), z) - v.begin();
        a[i][j] = a[i][j] - Fraction(1, 2);
      }
    }

    LU(m, a, r, c);
    solve(m, a, r, c, b);
cout<<"Case #"<<TT<<":"<<endl;
cout<<b[0].num<<"/"<<b[0].den<<endl;

//    printf("Case #%d:
", TT);
//    printf("%lld/%lld
", b[0].num, b[0].den);
  }

  return 0;
}