题意

题面：假设有一个 \(n+1\) 行 \(m+1\) 列的矩阵 \(A\)，下标从 \(0\) 开始，给定 \(A_{1,0}, A_{2, 0}, \cdots A_{n, 0}\)（即最左边一列的初始值），以及已知矩阵的第 \(1\) 行第 \(i\) 列为 \(2\underbrace {333\cdots3}_{i + 1 个 3}\)，如下所示： \[ \left(\begin{matrix} 0 &233 &2333 &23333 &\cdots \\ A_{1, 0} &A_{1, 1} &A_{1, 2} &A_{1, 3} &\cdots \\ A_{2, 0} &A_{2, 1} &A_{2, 2} &A_{2, 3} &\cdots \\ \vdots &\vdots &\vdots &\vdots &\ddots \end{matrix}\right) \] 并且已知对于 \(i, j \ge 1\)，有 \(A_{i, j} = A_{i - 1, j} + A_{i, j - 1}\)。求 \(A_{n, m}\)。

\(n \le 10, m \le 10^9\)。

解法

从数据范围可以得知我们必须使用矩阵快速幂加速递推，我们定义第 \(i\) 列的状态向量为一个 \(n + 2\) 行的列向量，并手动展开递推式消除同一列的项（非常重要，因为不然的话没办法推）得到转移矩阵： \[ \left(\begin{matrix} 1 \\ A_{i, 0} \\ A_{i, 1} \\ A_{i, 2} \\ A_{i, 3} \\ \vdots \end{matrix}\right) = \left(\begin{matrix} 1 &0 &0 &0 &0 &\cdots\\ 3 &10 &0 &0 &0 &\cdots\\ 3 &10 &1 &0 &0 &\cdots\\ 3 &10 &1 &1 &0 &\cdots\\ 3 &10 &1 &1 &1 &\cdots\\ \vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{matrix}\right) \left(\begin{matrix} 1 \\ A_{i - 1, 0} \\ A_{i - 1, 1} \\ A_{i - 1, 2} \\ A_{i - 1, 3} \\ \vdots \end{matrix}\right) \] 注意到我们怎么处理 \(2\underbrace {333\cdots3}_{i + 1 个 3}\) 的，我们发现 \(2\underbrace {3\cdots3}_{i + 1 个 3} = 2\underbrace {3\cdots3}_{i 个 3} \times 10 + 3\)，为了凑出 \(3\) 我们在矩阵当中引入 \(1\) 这多余的一行（这是在矩阵加速递推时引入常数项的常用技巧）（其实在这里直接引入 \(3\) 也可以啦，但是 \(1\) 的话更通用），这就是系数 \(3, 10\) 的由来。然后使用快速幂加速矩阵乘法即可，时间复杂度为 \(O(n^3\log m)\)：

#include <cstdio>

using namespace std;
typedef long long ll;
typedef int mat[13][13];
typedef int vec[13];
const int MOD = 10000007;
int n, m;
vec a;
mat b;

void mul(mat &x, vec &y) {
    vec z;
    for (int i = 1; i <= n + 2; i++) {
        z[i] = 0;
        for (int j = 1; j <= n + 2; j++)
            z[i] = (z[i] + 1LL * x[i][j] * y[j]) % MOD;
    }
    for (int i = 1; i <= n + 2; i++)
        y[i] = z[i];
}

void sqr(mat &x) {
    mat y;
    for (int i = 1; i <= n + 2; i++) {
        for (int j = 1; j <= n + 2; j++) {
            y[i][j] = 0;
            for (int k = 1; k <= n + 2; k++)
                y[i][j] = (y[i][j] + 1LL * x[i][k] * x[k][j]) % MOD;
        }
    }
    for (int i = 1; i <= n + 2; i++)
        for (int j = 1; j <= n + 2; j++)
            x[i][j] = y[i][j];
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        a[1] = 1, a[2] = 23;
        for (int i = 3; i <= n + 2; i++)
            scanf("%d", &a[i]);
        b[1][1] = 1;
        for (int i = 2; i <= n + 2; i++) {
            b[i][1] = 3, b[i][2] = 10;
            for (int j = 3; j <= i; j++)
                b[i][j] = 1;  
        }
        for (; m; m >>= 1) {
            if (m & 1) mul(b, a);
            sqr(b);
        }
        printf("%d\n", a[n + 2]);
    }
    return 0;
}