题目大意

有 $n$ 个三状态转轮（状态 $0,1,2$），初始全为 $0$。有 $m$ 种操作模式，第 $i$ 种模式选择 $a_i$ 个转轮转动 $1$ 次，$b_i$ 个转轮转动 $2$ 次，其余不动。每次操作随机选择一个模式，并在该模式的所有可能方案中随机选择一个。求进行 $k$ 次操作后，恰有 $i$ 个转轮在状态 $1$，$j$ 个转轮在状态 $2$ 的方案数，对 $10^9+9$ 取模。

算法思路

1. 状态表示与转移

状态定义：用 $dp[i][j]$ 表示有 $i$ 个转轮在状态 $1$，$j$ 个转轮在状态 $2$ 的方案数。

状态转移：对于每个模式 $(a,b)$，我们需要计算它如何改变当前状态：

• 转动规则：
  • 转动 $1$ 次：$0 \to 1$, $1 \to 2$, $2 \to 0$
  • 转动 $2$ 次：$0 \to 2$, $1 \to 0$, $2 \to 1$

转移计算：对于当前状态 $(i,j)$，枚举：

• 在 $a$ 个转动 $1$ 次的转轮中，有多少个来自状态 $0,1,2$
• 在 $b$ 个转动 $2$ 次的转轮中，有多少个来自状态 $0,1,2$

然后计算新的状态 $(i',j')$ 和对应的组合数系数。

2. 矩阵快速幂优化

由于 $k$ 可达 $10^{18}$，直接模拟不可行。我们将状态转移表示为矩阵形式，使用矩阵快速幂在 $O(\log k)$ 时间内完成 $k$ 次操作。

状态编码：状态 $(i,j)$ 满足 $i+j \leq n$，总状态数约为 $\frac{(n+1)(n+2)}{2}$。

矩阵构造：转移矩阵 $M$ 的 $M[(i,j)][(i',j')]$ 表示从状态 $(i,j)$ 到 $(i',j')$ 的转移系数。

3. 组合数预处理

预处理阶乘和逆元，使用公式计算组合数：

$$\binom{n}{a,b,c} = \frac{n!}{a!b!c!}, \quad a+b+c=n $$

关键代码解析

组合数计算

int comb(int n, int a, int b) {
    if (a < 0 || b < 0 || a + b > n) return 0;
    return 1LL * fac[n] * inv_fac[a] % MOD * inv_fac[b] % MOD * inv_fac[n - a - b] % MOD;
}

状态转移计算

核心部分是六重循环，枚举所有可能的转移情况：

for (int x0 = 0; x0 <= min(a, n - i - j); x0++) {
    for (int x1 = 0; x1 <= min(a - x0, i); x1++) {
        int x2 = a - x0 - x1;
        // ... 类似枚举 y0, y1, y2
        // 计算新状态和组合数系数
    }
}

矩阵快速幂

void matrix_pow(long long exp) {
    memset(res, 0, sizeof(res));
    res[0][0] = 1;  // 初始状态：全0
    
    while (exp) {
        if (exp & 1) matrix_mult(res, dp, res);
        matrix_mult(dp, dp, dp);
        exp >>= 1;
    }
}

复杂度分析

• 状态数：$O(n^2)$
• 单次转移：$O(n^4)$（经过优化剪枝）
• 总复杂度：$O(n^6 \log k)$

对于 $n \leq 120$，在优化后可以通过大部分测试点。

优化技巧

1. 状态剪枝：利用 $i+j \leq n$ 减少状态枚举
2. 组合数预处理：$O(1)$ 计算组合数
3. 矩阵稀疏性：转移矩阵相对稀疏，可进一步优化
4. 模运算优化：使用 long long 避免中间结果溢出

总结

本题是典型的组合计数 + 矩阵快速幂问题，主要难点在于：

1. 正确建模状态转移
2. 处理大规模指数 $k$
3. 优化高维状态转移的计算

通过将操作视为线性变换，并用矩阵快速幂加速，我们成功在 $O(\log k)$ 时间内解决了 $k$ 极大的问题。