巨大的表格 - 正经题解

这道题可以发现 $N$ 很小，但也没小到那种程度，注意到这题刚刚好能通过 $O(N^3)$ 的算法。

而且 $M$ 又这么大……还是递推题……

这就需要矩阵快速幂了。

由于矩阵乘法符合结合律，所以快速幂也适用于矩阵。这题就是一个很好的示例。

我们可以分别对于 $N=4,N=5$ 的情况构造矩阵，然后寻找规律。

任务：构造一个 $3\times 3$ 的矩阵，使得该矩阵乘以 $\begin{bmatrix} A_{3,i-1}\\A_{2,i-1}\\A_{1,i-1} \end{bmatrix}$ 得到 $\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i} \end{bmatrix}.$​

1. 化简结果矩阵，直到每一项可以用原矩阵里面的数乘以一个常数的和表示。

$$\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i} \end{bmatrix} =\begin{bmatrix} S\times A_{2,i}+T\times A_{3,i-1}\\S\times A_{1,i}+T\times A_{2,i-1}\\S\times A_{0,i}+T\times A_{1,i-1} \end{bmatrix} = \begin{bmatrix} T\times A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times i\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{2,i-1}+S\times T\times A_{1,i-1}+S^2\times i\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{1,i-1}+S\times i \end{bmatrix}$$

但这里出现了一个问题：$i$ 不是常数，也不能用前面的矩阵表示！

这也不是没有办法，在目标矩阵加两项：$i$ 和 $1$​ 就行了！

现在的任务：构造一个 $5\times 5$ 的矩阵，使得该矩阵乘以 $\begin{bmatrix} A_{3,i-1}\\A_{2,i-1}\\A_{1,i-1}\\i-1\\1 \end{bmatrix} \space$ 得到 $\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i}\\i\\1 \end{bmatrix}.$

1. 化简结果矩阵……

$$\begin{bmatrix} A_{3,i}\\A_{2,i}\\A_{1,i}\\i\\1 \end{bmatrix} = \begin{bmatrix} T\times A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times (i-1)+S^3\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{2,i-1}+S\times T\times A_{1,i-1}+S^2\times (i-1)+S^2\\\space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space \space T\times A_{1,i-1}+S\times (i-1)+S\\(i-1)+1\\1 \end{bmatrix}$$

OK！

2. 解方程！

设我们构造出的矩阵为 $\begin{bmatrix} a_1 & b_1 & c_1 & d_1 & e_1\\a_2 & b_2 & c_2 & d_2 & e_2\\a_3 & b_3 & c_3 & d_3 & e_3\\a_4 & b_4 & c_4 & d_4 & e_4\\a_5 & b_5 & c_5 & d_5 & e_5 \end{bmatrix}.$

根据矩阵乘法的定义，有：

$$\begin{cases} a_1\times A_{3,i}+b_1\times A_{2,i}+c_1\times A_{1,i}+d_1\times(i-1)+e_1\times 1=T\times A_{3,i-1}+S\times T\times A_{2,i-1}+ S^2\times T\times A_{1,i-1}+S^3\times (i-1)+S^3,\\ \\ a_2\times A_{3,i}+b_2\times A_{2,i}+c_2\times A_{1,i}+d_2\times(i-1)+e_2\times 1=T\times A_{2,i-1}+S\times T\times A_{1,i-1}+S^2\times (i-1)+S^2,\\ \\ a_3\times A_{3,i}+b_3\times A_{2,i}+c_3\times A_{1,i}+d_3\times(i-1)+e_3\times 1=T\times A_{1,i-1}+S\times (i-1)+S,\\ \\ a_4\times A_{3,i}+b_4\times A_{2,i}+c_4\times A_{1,i}+d_4\times(i-1)+e_4\times 1=i,\\ \\ a_5\times A_{3,i}+b_5\times A_{2,i}+c_5\times A_{1,i}+d_5\times(i-1)+e_5\times 1=1. \end{cases}$$

一一对应即可，可以轻松获得方程的解。

最终获得的矩阵为

$$\begin{bmatrix} T & S\times T & S^2\times T & S^3 & S^3\\ 0 & T & S\times T & S^2 & S^2\\ 0 & 0 & T & S & S\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}.$$

对于 $N=5$ 的情况，你们可以自己试一下，最终构造出的矩阵为

$$\begin{bmatrix} T & S\times T & S^2\times T & S^3\times T & S^4 & S^4\\ 0 & T & S\times T & S^2\times T & S^3 & S^3\\ 0 & 0 & T & S\times T & S^2 & S^2\\ 0 & 0 & 0 & T & S & S\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}.$$

我们发现，最后一行只有最后一列是 $1$，其余都是 $0$；第 $N$ 行只有后两列是 $1$，其余都是 $0$。

对于第 $i(1\le i\le N)$ 行，第 $i$ 列为 $T$，其余的均为下一行乘以 $S$。

构造方法如下：

mtx[n][n] = 1;
mtx[n - 1][n - 1] = mtx[n - 1][n] = 1;
for(int i = n - 2; i >= 0; i--){
	mtx[i][i] = t;
	for(int j = i + 1; j <= n; j++){
		mtx[i][j] = mtx[i + 1][j] * s % mod;
	}
}

初始矩阵：

$$\begin{bmatrix} \vdots\\ A_{3,0}\\A_{2,0}\\A_{1,0}\\0\\1 \end{bmatrix}.$$

然后就可以快速幂了。

矩阵快速幂和普通快速幂差不多，但注意矩阵乘法不满足交换律，所以顺序不能搞混！

#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n, m, s, t;
int b[35];
int mtx[40][40]; 
struct matrix{
	int a[40][40];
	matrix(){
		memset(a, 0, sizeof(a));
	}
	void _1(){
		for(int i = 0; i < n - 1; i++) a[n - i - 2][0] = b[i];//初始化，A_{i,0}
		a[n][0] = 1;
	}
	void _2(){
		for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) a[i][j] = mtx[i][j];//乘数
	}
	matrix operator * (const matrix &b) const{//矩阵乘法
		matrix tmp;
		for(int i = 0; i < 35; i++){
			for(int j = 0; j < 35; j++){
				for(int k = 0; k < 35; k++){
					tmp.a[i][j] += a[i][k] * b.a[k][j] % mod;
					tmp.a[i][j] %= mod;
				}
			}
		}
		return tmp;
	}
};

matrix pow(int time){//快速幂
	matrix tmp, a;
	tmp._1();
	a._2();
	while(time){
		if(time & 1) tmp = a * tmp;
		a = a * a, time >>= 1;
	}
	return tmp;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> s >> t;
	for(int i = 0; i < n - 1; i++) cin >> b[i];
	mtx[n][n] = 1;//构造乘法矩阵
	mtx[n - 1][n - 1] = mtx[n - 1][n] = 1;
	for(int i = n - 2; i >= 0; i--){
		mtx[i][i] = t;
		for(int j = i + 1; j <= n; j++){
			mtx[i][j] = mtx[i + 1][j] * s % mod;
		}
	}
	int q;
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		cout << pow(y).a[n - x - 1][0] << '\n';
	}

	return 0;
}

时间复杂度 $O(QN^3\log M)$。

初次推矩阵耗时可能长一些，但熟练之后两三分钟就可以完成了。加油！