233矩阵

题目描述

在我们的日常生活中，我们经常使用 233 来表达我们的感受。

实际上，我们可能会说 2333, 23333 或 233333...... 意思相同。

假设我们有一个名为 233矩阵 的矩阵。

矩阵定义

第一行规则

在第一行，它将包含 233, 2333, 23333...（这意味着 $a_{0,1} = 233$，$a_{0,2} = 2333$，$a_{0,3} = 23333...$）。

递推规则

在 233 矩阵中，满足：

$$a_{i,j} = a_{i-1,j} + a_{i,j-1} \quad (i,j \neq 0)$$

边界条件

给定 $a_{1,0}, a_{2,0}, ..., a_{n,0}$（第0列的初始值）

问题

现在给定 $a_{1,0}, a_{2,0}, ..., a_{n,0}$，请求出在 233 矩阵中 $a_{n,m}$ 的值。

输入格式

输入包含多组数据，请处理至文件末尾。

每组数据包括两行：

• 第一行包含两个整数 $n, m$
• 第二行包含 $n$ 个整数，表示 $a_{1,0}, a_{2,0}, ..., a_{n,0}$

输出格式

每组数据输出一个整数，表示 $a_{n,m} \mod 10000007$ 的值。

每个结果占一行。

数据范围

• $1 \le n \le 10$
• $1 \le m \le 10^9$
• $0 \le a_{i,0} < 2^{31}$

输入样例

1 1
1
2 2
0 0
3 7
23 47 16

输出样例

234
2799
72937

样例解释

第一个测试用例：$n=1, m=1, a_{1,0}=1$

构建233矩阵：

第0行（特殊定义）：

• $a_{0,1} = 233$
• $a_{0,2} = 2333$
• $a_{0,3} = 23333$
• ...（以此类推）

第0列（给定）：

• $a_{1,0} = 1$

计算：

• $a_{0,1} = 233$
• $a_{1,1} = a_{0,1} + a_{1,0} = 233 + 1 = 234$

输出：234

第二个测试用例：$n=2, m=2, a_{1,0}=0, a_{2,0}=0$

矩阵计算：

第0行：

• $a_{0,1} = 233$
• $a_{0,2} = 2333$

第0列：

• $a_{1,0} = 0$
• $a_{2,0} = 0$

计算过程：

1. $a_{1,1} = a_{0,1} + a_{1,0} = 233 + 0 = 233$
2. $a_{1,2} = a_{0,2} + a_{1,1} = 2333 + 233 = 2566$
3. $a_{2,1} = a_{1,1} + a_{2,0} = 233 + 0 = 233$
4. $a_{2,2} = a_{1,2} + a_{2,1} = 2566 + 233 = 2799$

输出：2799

第三个测试用例：$n=3, m=7, a_{1,0}=23, a_{2,0}=47, a_{3,0}=16$

计算过程复杂，需要推导通项公式

最终结果：$a_{3,7} \mod 10000007 = 72937$

矩阵推导

递推公式

$$a_{i,j} = a_{i-1,j} + a_{i,j-1}$$

这类似于二维递推，可以写成矩阵形式。

列向量表示

定义列向量：

$$\mathbf{A}_j = \begin{bmatrix} a_{1,j} \\ a_{2,j} \\ \vdots \\ a_{n,j} \end{bmatrix}$$

递推关系

根据 $a_{i,j} = a_{i-1,j} + a_{i,j-1}$，有：

对于 $i = 1$：$a_{1,j} = a_{0,j} + a_{1,j-1}$ 对于 $i > 1$：$a_{i,j} = a_{i-1,j} + a_{i,j-1}$

设 $C_j = a_{0,j}$（第一行的值），则有：

$$\mathbf{A}_j = M \cdot \mathbf{A}_{j-1} + \mathbf{C}_j$$

其中 $M$ 是一个 $n \times n$ 的矩阵：

$$M = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 \\ 1 & 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 & 1 \end{bmatrix}$$

和

$$\mathbf{C}_j = \begin{bmatrix} C_j \\ 0 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$

第一行的值

$a_{0,j} = 2333...3$（$j$ 个 3，前面加 23） 具体：

• $a_{0,1} = 233$
• $a_{0,2} = 2333 = 233 \times 10 + 3$
• $a_{0,3} = 23333 = 2333 \times 10 + 3$

通项：$a_{0,j} = \frac{23 \times 10^{j+1} + 7}{9} \mod 10000007$

矩阵快速幂

由于 $m$ 很大（最大 $10^9$），需要矩阵快速幂。

状态向量可以扩展为：

$$\mathbf{X}_j = \begin{bmatrix} \mathbf{A}_j \\ 1 \end{bmatrix}$$

则：

$$\mathbf{X}_j = T \cdot \mathbf{X}_{j-1}$$

其中 $T$ 是 $(n+1) \times (n+1)$ 的转移矩阵。

算法步骤

1. 构建 $(n+1) \times (n+1)$ 的转移矩阵 $T$
2. 计算 $T^m$
3. 应用初始条件得到 $\mathbf{X}_m$
4. 提取 $a_{n,m}$

模运算

所有计算需要在模 $10000007$ 下进行。

时空限制

• 时间限制：1秒
• 空间限制：64MB