题意

维护一个集合 $S$，表示后缀的数 $\text{mod } k$ 组成的集合。称集合 $S$ 为当前状态，初始为空集。

每次打字等同于随机选择 $t \in [0, B - 1]$，令 $S \leftarrow \text{nxt}$。其中集合 $\text{nxt}$ 表示打字后的集合，并称 $\text{nxt}$ 为后继状态。

可以得到 $\text{nxt} = \bigcup \limits_{i \in S \cup \{0\}} (i \cdot B + t) \bmod k$。

目标是使得 $0 \in S$。求达成目标的期望次数。

方程式

设 $f(S)$ 表示当前集合为 $S$ 时还需的期望次数。则当 $0 \in S$ 时，$f(S) = 0$；否则

$$f(S) = 1 + \dfrac{1}{B} \sum_{t \in [0, B - 1]} f(\text{nxt}) $$

当 $t \bmod k$ 相同时 $\text{nxt}$ 相同。所以合并这些状态得到

$$f(S) = 1 + \dfrac{1}{B} \sum_{t \in [0, k - 1]} \left \lfloor \dfrac{B + k - 1 - t}{k} \right \rfloor \cdot f(\text{nxt}) $$

算法 $1$：$B \bmod k = 0$

当 $B \bmod k = 0$ 时，$\text{nxt}$ 与 $S$ 无关。

目标转化为 $t \bmod k = 0$，每次打字完成目标的概率为 $\dfrac{1}{k}$。

设 $f(\varnothing) = x$，则 $x = 1 + \left ( 1 - \dfrac{1}{k} \right ) x$，解得 $x = k$，即答案为 $k$。

时间复杂度：$O(1)$

算法 $2$：$\gcd(B, k) = 1$

结论：在达到目标前 $|S|$ 单调递增，其中 $|S|$ 表示集合 $S$ 的元素个数。
证明：因为逆元存在，所以对于任意 $i$，$i$ 和 $i \cdot B \bmod k$ 一一对应。
如果 $0 \notin S$，则 $\left | \bigcup \limits_{i \in S \cup \{0\}} (i \cdot B + t) \right | = |S \cup \{0\}| = |S| + 1$。
即在达到目标前 $|S|$ 随每次打字增加 $1$。

所以可以按照 $|S|$ 降序进行 DP。

优化：用位运算加速计算 $\text{nxt}$ 的过程。这可以使复杂度减少一个 $k$ 的因子。

时间复杂度：$O(2^k \times k) \sim O(2^k \times k^2)$

算法 $3$：$\gcd(B, k) \geq 2$

结论：最多只有 $2^{\frac{k}{\gcd(B, k)}} \cdot \gcd(B, k)$ 种可能的 $S$。
证明：对于任意 $i$，$i \cdot B \bmod k$ 是 $\gcd(B, k)$ 的倍数。
即 $S$ 的元素减去 $t$ 的集合一定是所有 $\gcd(B, k)$ 的倍数组成集合的子集，有 $2^{\frac{k}{\gcd(B, k)}}$ 种可能。
加上 $t$ 后乘以 $\gcd(B, k)$ 即得到答案。

以上只是理论上界，实际（不包含 $0$ 的）可能的 $S$ 的状态数是一个更小的值。

所以可以直接列出转移方程，再用高斯消元解方程组。

优化：只计算本质不相同的 $S$。定义“本质不相同”为 $\text{nxt}$ 不相同（，且 $\text{nxt}$ 也“本质不相同”）。因为本质相同的 $S$ 的答案一定相同，故可以合并为同一状态。

优化：在高斯消元时只计算非零项。因为矩阵较稀疏，可以跳过许多零，从而减少复杂度。

优化（来自验题人）：在解方程时将转移关系建图，在用 tarjan 缩点后每个强连通分量的点中高斯消元，点之间的 DAG 则直接 DP。

时间复杂度：$O(N^3)$，$N$ 为状态数

子任务

结合算法 $1, 2$ 及优化可以通过 $k$ 为 $1$ 或质数的测试点。

结合算法 $2, 3$ 及优化可以通过所有测试点。