一、内容
https://blog.csdn.net/qq_41280600/article/details/103083637 Acwing这里的显示不辽 也不想弄了就看博客的吧。。。。。
二、思路
- 首先我们推一下从第一列得到第二列的结果:
$$\left[\begin{matrix} … \\\…\\\… \\\… \\\… \\\… \\\ \end{matrix} \right] \left[\begin{matrix} 23 \\ a【1】\\ a【2】\\ a【3】\\…\\ a【K】 \end{matrix} \right] = \left[\begin{matrix} 233 \\ a【1】 + 233 \\ a【1】+ a【2】 + 233\\ a【1】+ a【2】+ a【3】+233\\…\\ a【1】+ a【2】+a【3】 + ....+ a【K】+233 \end{matrix} \right] $$
$$= \left[\begin{matrix} 10 * a【0】+ 3 \\ a【1】 + 10 * a【0】+ 3 \\ a【2】 + a【1】 + 10 * a【0】+ 3 \\ a【3】+ a【1】 + 10 * a【0】+ 3 \\…\\ a【K】+ … + a【1】 + 10 * a【0】+ 3 \end{matrix} \right] = 新的一列$$
第三列的结果,在第二列的基础上得来。和上面的推导一样,这里就不再给出。 - 我们设左边未知矩阵为G,G乘以某一列的矩阵就会得到新的一列,我们再将G乘以新的一列又会得到下一列,故我们只需要求出G^m^,再将G^m^乘以一列,最后得出的结果就是m列的矩阵了。
- 我们根据上面的推导可以很容易推出G矩阵
$$G = \left[\begin{matrix} 10 &0 & 0&0 &…&1 \\10 &1 & 0&0 &…&1\\10 &1 & 1&0 &…&1 \\ 10 &1 & 1&1 &…&1 \\0 &0&0&0&…&1\\ \end{matrix} \right]$$ - 第一列的矩阵为:
$$ A= \left[\begin{matrix} 23 \\ a【1】【0】\\ a【2】【0】\\ a【3】【0】\\…\\ a【K】【0】\\3 \end{matrix} \right]$$
最后一个元素为3,是因为每次和G矩阵相乘都会多+1个3,所以G矩阵的n+1列全部是1,这样和A相乘的话,每次都会加上3才能构成23333....这样的组合。
- 由于矩阵相乘过程中会有很多次的取余操作,这样会很消耗时间,所以我们应该尽量减少取余操作。我们将矩阵设置为64位整型,这样当数据量大的时候会节省很多时间。
三、代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
using namespace std;
const int MOD = 10000007, N = 13;
using namespace std;
struct matrix {
ll m[N][N];
matrix() {
memset(m, 0, sizeof(m));
}
};
int n, m, rec[N];
matrix mul(matrix a, matrix b) {
matrix ans;
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= n + 1; j++) {
for (int k = 0; k <= n + 1; k++) {
ans.m[i][j] = (ans.m[i][j] + a.m[i][k] * b.m[k][j]);
}
ans.m[i][j] %= MOD;
}
}
return ans;
}
void f() {
matrix g;
//1.每次初始化下g数组
for (int i = 0; i <= n; i++) {
g.m[i][0] = 10;
g.m[i][n + 1] = 1;
for (int j = 1; j < i + 1; j++) {
g.m[i][j] = 1;
}
}
//将n+1列变成1
g.m[n + 1][n + 1] = 1;
//2.矩阵快速幂
matrix A;
for (int i = 0; i <= n + 1; i++) A.m[i][i] = 1; //变为单位矩阵
while (m) {
if (m & 1) A = mul(A, g); //改变的是ans这个数组
g = mul(g, g);
m >>= 1;
}
int ans = 0;
//3.最后将A 和 rec相乘
for (int k = 0; k <= n + 1; k++) {
ans = (ans + A.m[n][k] * rec[k]) % MOD;
}
//输出结果
printf("%d\n", ans);
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
//初始化一列的值
rec[0] = 23;
rec[n + 1] = 3;
for (int i = 1; i <= n; i++ ){
scanf("%d", &rec[i]);
}
f();
}
return 0;
}