「COCI 2023.2」Bojanje 题解

题目大意

有 $n$ 个部分，初始每个部分颜色不同。进行 $t$ 次操作，每次操作：

1. 均匀随机选择下标 $i$
2. 均匀随机选择下标 $j$，将第 $j$ 部分涂成第 $i$ 部分的颜色

求最终画作中至少有 $k$ 种不同颜色的概率，对 $10^9+7$ 取模。

解题思路

核心观察

1. 状态表示：可以用整数划分来表示颜色分布状态
   • 如 [3,1] 表示两种颜色，分别有 3 个和 1 个部分
2. 马尔可夫过程：每次操作只依赖于当前状态
3. 状态数有限：$n \leq 10$，划分数 $p(10)=42$ 可接受

算法步骤

1. 生成所有状态

使用 DFS 生成所有整数划分：

void dfs(int d, int lst, int s) {
    if (s == n) {
        vector<ll> b;
        for (int i = 1; i < d; ++i) 
            b.pb(a[i]);
        mp[b] = ++tot;
        vc[tot] = b;
        return;
    }
    for (int i = lst; s + i <= n; ++i) {
        a[d] = i;
        dfs(d + 1, i, s + i);
    }
}

2. 构建转移矩阵

对于每个状态 $v$，枚举所有可能的 $(i,j)$ 选择：

for (int j = 0; j < (int)v.size(); ++j) {
    for (int k = 0; k < (int)v.size(); ++k) {
        auto w = v;
        --w[j]; ++w[k];  // 从颜色j取一个部分染成颜色k
        sort(w.begin(), w.end());
        while (w.size() && !w[0]) 
            w.erase(w.begin());  // 删除大小为0的颜色
        int x = mp[v], y = mp[w];
        A.a[x][y] = (A.a[x][y] + v[j] * v[k] * inv) % mod;
    }
}

转移概率计算：

• 选择颜色 $j$ 的概率：$\frac{v_j}{n}$
• 选择颜色 $k$ 的概率：$\frac{v_k}{n}$
• 总概率：$\frac{v_j v_k}{n^2}$

3. 矩阵快速幂

由于 $t$ 可达 $10^{18}$，使用矩阵快速幂：

A = qpow(A, K);  // 注意代码中K对应题目中的t

4. 计算答案

初始状态为 [1,1,...,1]（$n$ 个 1），对应状态编号 1：

for (int i = 1; i <= tot; ++i) {
    if ((int)vc[i].size() >= m) {  // 注意代码中m对应题目中的k
        ans = (ans + A.a[1][i]) % mod;
    }
}

关键代码解析

状态转移理解

当从颜色 $j$ 选择一个部分染成颜色 $k$ 时：

• 如果 $j = k$：状态不变
• 如果 $j \neq k$：
  • 颜色 $j$ 大小减 1（可能消失）
  • 颜色 $k$ 大小加 1
  • 需要重新排序并清理大小为 0 的颜色

模运算处理

• 概率分母 $n^2$ 的逆元：inv = qpow(n * n, mod - 2)
• 使用费马小定理计算模逆元

复杂度分析

• 状态数：$p(n)$，$n=10$ 时 $p(10)=42$
• 矩阵大小：$42 \times 42$
• 矩阵快速幂：$O(p(n)^3 \log t) \approx 42^3 \times \log(10^{18}) \approx 3 \times 10^5$ 次运算
• 完全可行

样例验证

样例1：n=2, t=1, k=2

• 状态：[2], [1,1]
• 初始状态 [1,1]（2种颜色）
• 一次操作后：
  • 保持 [1,1] 的概率：$\frac{1}{2}$（选择相同部分或不同部分的相同颜色）
  • 变为 [2] 的概率：$\frac{1}{2}$
• 答案：$\frac{1}{2} = 500000004 \pmod{10^9+7}$

样例2：n=10, t=2, k=5

• 2次操作最多减少2种颜色
• 从10种颜色变为至少8种颜色 $\geq 5$
• 答案：$1$

总结

本题的解法体现了：

1. 状态压缩：用整数划分表示复杂的颜色分布
2. 矩阵建模：将随机过程转化为线性代数问题
3. 算法优化：用快速幂处理大指数
4. 模运算技巧：概率的模表示和计算

是一个典型的"状态数少但迭代次数多"问题的标准解法。