Chiitoitsu（概率DP）

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int N = 150, M = 10, mod = 1e9 + 7;

char s[N];
map<string, int> mp;
ll f[N][M];

ll qmi(ll a, ll b)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x)
{
    return qmi(x, mod - 2);
}

ll dfs(int a, int b)
{
    ll &v = f[a][b];
    if(v >= 0) return v;
    ll t = a - 3 * (13 - 2 * b);
    if(t > 0) {
        ll tmp = inv(a);
        ll p1 = t * tmp % mod, p2 = 3 * (13 - 2 * b) * tmp % mod;
        v = (1 + p1 * dfs(a - 1, b) + p2 * dfs(a - 1, b + 1)) % mod;
    }
    else {
        v = (1 + dfs(a - 1, b + 1)) % mod;
    }
    return v;
}

int main()
{
    int T;
    scanf("%d", &T);
    memset(f, -1, sizeof f);
    for(int i = 0; i < N; i ++) f[i][7] = 0;
    for(int cas = 1; cas <= T; cas ++) {
        scanf("%s", s + 1);
        mp.clear();
        for(int i = 1; i <= 13; i ++) {
            string t = "";
            t += s[2 * i - 1], t += s[2 * i];
            mp[t] ++;
        }
        int cnt = 0;
        for(auto p : mp) {
            if(p.second >= 2) cnt ++;
        }
        printf("Case #%d: %lld\n", cas, dfs(123, cnt));
    }
    return 0;
}