Codeforces 482C Game with Strings：狀壓 DP + 概率期望巧解

問題重述

給定 n 個長度為 m 的字符串，等概率隨機藏起一個。玩家每步等概率詢問一個未揭示的位置，直到能唯一確定藏起的字符串。求玩家的期望詢問步數。
約束：n ≤ 50, m ≤ 20。

核心思路：狀壓 DP 消除 n 因子

狀態 mask（m 位）表示已揭示的位置集合。
若直接枚舉藏起的字符串（O(n)），再對每個狀態轉移（O(m·2^m)），總複雜度 O(n·m·2^m) 會 TLE。

關鍵觀察：對於固定的 mask，「無法區分的字符串集合」僅取決於 mask 本身，與具體藏哪個串無關。預處理 f[mask] 表示在 mask 下仍無法區分的字符串集合（位掩碼），則可將複雜度降至 O(m·2^m)。

預處理 f[mask]

1. 對每對不同字符串 (i, j)，計算它們相同字符的位置掩碼 same；則在 same 狀態下 i, j 無法區分，令 f[same] |= (1<<j)。
2. 對所有 mask 從大到小枚舉，若 mask 包含位 k，則 f[mask ^ (1<<k)] |= f[mask]（揭示更少位置時，無法區分的串只會更多）。

期望 DP

• dp[mask]：從空集走到 mask 的概率（或稱到達該狀態的期望權重）。
• 初始 dp[0] = 1。
• 對每個 mask，設已揭示位數為 c，則每個未揭示位被選中的概率為 1/(m-c)，轉移 dp[mask | (1<<k)] += dp[mask] / (m-c)。
• 若 f[mask] != 0（至少有兩個串無法區分），則對其中每個可能的藏串，還需再走一步，貢獻 dp[mask] 到答案。

完整代碼（GNU++17）

#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 25;
int n, len;
char str[N][M];
long long f[1 << 20], bin[N];
double dp[1 << 20], ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> str[i];
    len = strlen(str[0]);
    bin[0] = 1;
    for (int i = 1; i < N; ++i) bin[i] = bin[i-1] << 1;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) if (i != j) {
            int same = 0;
            for (int k = 0; k < len; ++k)
                if (str[i][k] == str[j][k]) same |= bin[k];
            f[same] |= bin[j];
        }

    for (int mask = bin[len] - 1; mask >= 0; --mask)
        for (int k = 0; k < len; ++k)
            if (mask & bin[k]) f[mask ^ bin[k]] |= f[mask];

    dp[0] = 1;
    for (int mask = 0; mask < bin[len]; ++mask) {
        int c = __builtin_popcount(mask);
        for (int k = 0; k < len; ++k)
            if (!(mask & bin[k]))
                dp[mask | bin[k]] += dp[mask] / (len - c);
        for (int j = 0; j < n; ++j)
            if (f[mask] & bin[j]) ans += dp[mask];
    }
    cout << fixed << setprecision(10) << ans / n << '\n';
    return 0;
}

複雜度分析

• 預處理 f：O(n²·m + m·2^m)；
• DP 轉移：O(m·2^m)；
• 總計 O(m·2^m)，m ≤ 20 時極快。