YC278A [ 20240420 CQYC省选模拟赛 T1 ] 作画（paint)

题意

给定排列 \(S\)，最初 \(S_i = i\)。

每次进行以下操作，进行 \(t\) 次。

• 选择下标 \(i, j\)，使得 \(S_i = S_j\)。

求进行 \(t\) 次后，\(S\) 有至少 \(k\) 种数字的概率。

\(n \le 10, t \le 10 ^ {18}\)。

Sol

考虑概率转方案，变为有多少种方案使得最终状态有 \(k\) 种数字。

不难注意到我们并不关心每个位置到底是哪些数。

我们只关心每种数到底有多少个。

考虑一种状态，\(f_i\) 表示第 \(i\) 种颜色的个数。

因为我们不关心具体的颜色，因此可以让 \(f\) 满足偏序关系。

注意到总状态数非常少，对于 \(n = 10\) 时，总状态数只有 \(42\) 种。

直接上矩阵快速幂转移即可。