HDOJ 5229 ZCC loves strings：博弈論 + 組合數學求先手勝率

問題同 BestCoder Round #41 B 題

N 字符串，隨機選兩個不同串遊戲。先手 Miss G。操作：刪末尾字符，或兩串相同非空時清空。求先手勝概率既約分數。

核心邏輯（同 4149）

• 長度奇偶不同 → 先手勝
• 完全相同 → 先手勝（操作 B）
• 其他情況先手負

統計 odd、even、相同串對數 samePairs。win = odd*even + samePairs，total = C(N,2)，約分輸出。

完整代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    int T; scanf("%d", &T);
    for (int tc=1; tc<=T; ++tc) {
        int n; scanf("%d", &n);
        map mp;
        LL odd=0, even=0, same=0;
        string s;
        for (int i=0; i> s;
            if (mp.count(s)) same += mp[s], mp[s]++;
            else mp[s]=1;
            (s.size()%2 ? odd : even)++;
        }
        LL win = odd*even + same;
        LL tot = (LL)n*(n-1)/2;
        if (win==0) puts("0/1");
        else {
            LL g = __gcd(win, tot);
            printf("%lld/%lld\n", win/g, tot/g);
        }
    }
    return 0;
}