问题形式化

给定 $k \times k$ 矩阵 $M$，以及二进制字符串 $n = (b_{m-1} b_{m-2} \dots b_0)_2$，其中 $m \le 10000$，$k \le 50$，求

$M^n \pmod{1000000007}$

1. 普通快速幂公式（整数指数）

若 $n$ 为整数，快速幂算法基于二进制分解：

$ n = \sum_{i=0}^{m-1} b_i 2^i, \quad b_i \in \{0,1\} $

则 $ M^n = \prod_{i=0}^{m-1} \left(M^{2^i}\right)^{b_i} $

计算过程： $ \begin{aligned} & \text{令 } A = I,\quad B = M \\ & \text{for } i = 0 \text{ to } m-1: \\ & \quad \text{if } b_i = 1: \quad A \leftarrow A \cdot B \\ & \quad B \leftarrow B^2 \end{aligned} $ 最终 $A = M^n$。

2. 二进制字符串的处理

由于 $n$ 以二进制字符串 $s = s_0 s_1 \dots s_{m-1}$ 给出（$s_0$ 是最高位，$s_{m-1}$ 是最低位），两种顺序：

方法 A：从最低位到最高位（需要先存储字符串）

等价于 $b_0$ 对应 $s_{m-1}$，$b_{m-1}$ 对应 $s_0$。

公式： $ \begin{aligned} & A \leftarrow I,\quad B \leftarrow M \\ & \text{for } j = m-1 \text{ down to } 0: \\ & \quad \text{if } s_j = '1': \quad A \leftarrow A \cdot B \\ & \quad B \leftarrow B^2 \end{aligned} $

方法 B：从最高位到最低位（更自然）

设 $n$ 的二进制表示为 $s_0 s_1 \dots s_{m-1}$（$s_0$ 是最高位）。

令 $n_i$ 为前 $i+1$ 位组成的数的值，即 $n_0 = s_0,\quad n_{i} = 2 n_{i-1} + s_i$

那么： $M^{n_i} = (M^{n_{i-1}})^2 \cdot M^{s_i}$

算法： $ \begin{aligned} & A \leftarrow I \\ & \text{for } i = 0 \text{ to } m-1: \\ & \quad A \leftarrow A^2 \\ & \quad \text{if } s_i = '1': \quad A \leftarrow A \cdot M \end{aligned} $

3. 正确性证明（方法 B）

归纳法：

• 初始：$i = -1$ 时 $n = 0$，$A = I = M^0$。
• 假设 $i-1$ 时 $A = M^{n_{i-1}}$。
• 第 $i$ 步：
  • 先平方：$A \leftarrow (M^{n_{i-1}})^2 = M^{2 n_{i-1}}$
  • 若 $s_i = 1$：$A \leftarrow M^{2 n_{i-1}} \cdot M = M^{2 n_{i-1} + 1} = M^{n_i}$
  • 若 $s_i = 0$：$A$ 保持不变，即 $M^{2 n_{i-1}} = M^{n_i}$（因为 $n_i = 2 n_{i-1}$）。

因此循环结束时 $A = M^{n_{m-1}} = M^n$。

4. 复杂度分析

• 一次 $k \times k$ 矩阵乘法需要 $O(k^3)$ 次算术运算（模 $10^9+7$）。
• 循环次数 = 二进制长度 $m \le 10000$。
• 每次循环：1 次矩阵平方，可能加 1 次矩阵乘法。
• 总运算量：$O(m \cdot k^3) \approx 10000 \cdot 50^3 = 1.25 \times 10^9$ 次模运算。
• 模运算用 64 位整数可较快完成，在时限内可行。

5. 数学视角

这本质上是矩阵的乘法半群上的快速幂算法，不依赖数的整数表示，只依赖二进制位的顺序和矩阵的结合律。

公式总结： $ M^n = \left( \cdots \left( \left( I^2 \cdot M^{s_0} \right)^2 \cdot M^{s_1} \right)^2 \cdots \right)^2 \cdot M^{s_{m-1}} $ 其中 $M^{s_i}$ 在 $s_i=1$ 时为 $M$，否则为 $I$。

这样，我们完全用数学公式和推导描述了该问题的解法，无需代码。