题解

骰子个数 $d\le 6$，每颗骰子 6 个面。一次掷骰的结果可视为长度为 $d$ 的符号序列（按骰子编号记录朝上的面），共 $6^d\le 46656$ 种。合法状态判定：把序列排序后，若与字典中某个单词的排序结果相同，则已达成目标。

可在任意状态选择任意非空子集的骰子重新掷，代价为 1，期望转移为重新掷子集后各面等概率独立。记 $V(s)$ 为从状态 $s$ 达成目标所需的最优期望掷骰次数，则有 Bellman 方程：

$$V(s)=\begin{cases} 0,& s\text{为目标；}\\ \min\limits_{0\ne m\subseteq\{1..d\}}\Bigl(1+\mathbb E[V(s')]\Bigr),&\text{否则，} \end{cases} $$

其中 $s'$ 为在状态 $s$ 下重掷子集 $m$ 后的随机新状态。选择子集仅影响未掷骰子的面值，故对给定 $m$ 的期望仅依赖 $s$ 在补集上的面值。

预处理

• 将字典中每个单词排序后存入哈希表。
• 枚举全部 $6^d$ 状态，生成其符号序列、排序后判定是否为目标。
• 预存状态的每个骰子面下标（Base-6 编码），以及 $6^i$ 权值便于替换某骰子面。

期望转移的子集 DP

设 avg[m][s] 表示在状态 $s$ 上重掷集合 $m$ 后的 $\mathbb E[V]$。有递推： avg[0]=V，若 $m$ 的最低位为 $b$，则

avg[m][s] = (1/6) * Σ_{f=0..5} avg[m \ {b}][s 之第 b 颗骰子改为面 f]

按子集递增顺序计算，可在一轮 O(6^d * d * 2^{d-1}) 时间得到所有 avg。

值迭代

用上述转移计算一轮新的 $V$：

newV[s] = 0                        if s is goal
newV[s] = 1 + min_{m!=0} avg[m][s] otherwise

反复迭代直至收敛（最大变化量 < 1e-12 或迭代上限）。状态数仅 46656，单轮约千万级操作，可轻松通过。

初始期望为“先掷所有骰子一次”：

$$\text{Ans} = 1 + \frac{1}{6^d}\sum_s V(s).$$

若不存在任何目标状态则输出 impossible。

复杂度

• 状态数 $6^d\le 46656$；
• 单轮迭代 $O(6^d \cdot d \cdot 2^{d-1})$，空间 $O(6^d \cdot 2^d)$ 存 avg。

参考代码

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

const double INF = 1e100;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int d, w;
    if (!(cin >> d >> w)) return 0;
    const int SIG = 36;
    auto id = [](char ch) { return ('A' <= ch && ch <= 'Z') ? ch - 'A' : 26 + (ch - '0'); };
    auto unmap = [](int v) { return (v < 26) ? char('A' + v) : char('0' + v - 26); };

    vector<array<int, 6>> faceSym(d);
    for (int i = 0; i < d; ++i) {
        string s; cin >> s;
        for (int j = 0; j < 6; ++j) faceSym[i][j] = id(s[j]);
    }

    unordered_set<string> dict;
    dict.reserve(w * 2);
    string word;
    for (int i = 0; i < w; ++i) {
        cin >> word;
        sort(word.begin(), word.end());
        dict.insert(word);
    }

    int S = 1;
    vector<int> pow6(d);
    pow6[0] = 1;
    for (int i = 1; i < d; ++i) pow6[i] = pow6[i - 1] * 6;
    for (int i = 0; i < d; ++i) S *= 6;

    vector<array<int, 6>> digit(S);
    for (int s = 0; s < S; ++s) {
        int x = s;
        for (int i = 0; i < d; ++i) { digit[s][i] = x % 6; x /= 6; }
    }

    vector<char> isWord(S, 0);
    int wordStates = 0;
    string buf(d, 'A'), sortedBuf;
    for (int s = 0; s < S; ++s) {
        for (int i = 0; i < d; ++i) buf[i] = unmap(faceSym[i][digit[s][i]]);
        sortedBuf = buf; sort(sortedBuf.begin(), sortedBuf.end());
        if (dict.count(sortedBuf)) { isWord[s] = 1; ++wordStates; }
    }
    if (wordStates == 0) { cout << "impossible\n"; return 0; }

    int maskCnt = 1 << d;
    vector<double> V(S, 0.0), newV(S, 0.0);
    vector<vector<double>> avg(maskCnt, vector<double>(S, 0.0));

    const double EPS = 1e-12;
    for (int iter = 0; iter < 200; ++iter) {
        avg[0] = V;
        for (int m = 1; m < maskCnt; ++m) {
            int b = __builtin_ctz(m);
            int pm = m ^ (1 << b);
            for (int s = 0; s < S; ++s) {
                double acc = 0.0;
                int curDigit = digit[s][b];
                int base = s - curDigit * pow6[b];
                for (int f = 0; f < 6; ++f) acc += avg[pm][base + f * pow6[b]];
                avg[m][s] = acc / 6.0;
            }
        }

        double maxDiff = 0.0;
        for (int s = 0; s < S; ++s) {
            if (isWord[s]) { newV[s] = 0.0; continue; }
            double best = INF;
            for (int m = 1; m < maskCnt; ++m) best = min(best, 1.0 + avg[m][s]);
            newV[s] = best;
            maxDiff = max(maxDiff, fabs(newV[s] - V[s]));
        }
        V.swap(newV);
        if (maxDiff < EPS) break;
    }

    double sumV = 0.0;
    for (double v : V) sumV += v;
    double ans = 1.0 + sumV / S; // roll all dice once
    cout.setf(ios::fixed);
    cout << setprecision(9) << ans << "\n";
    return 0;
}