【矩阵快速幂】233 Matrix HDU - 5015
程序员文章站
2022-07-03 18:46:40
...
Think:
1知识点:矩阵快速幂
2题意:定义一个233矩阵,第一行形如233, 23333, 233333, 233…(即a[0][1] = 233, a[0][2] = 2333,a[0][3] = 23333, a[0][4] = 233…),现输入n列的第一个数(即a[1][0], a[2][0], … , a[n][0]),询问a[n][m](n ≤ 10,m ≤ 1e9)的值
3思路:
(1):由题意可知m范围可达到1e9,进而思考是否可寻找到第m列和第m-1列的关系
第一列:
a1
a2
a3
a4
则第二列
23*10+3 + a1
23*10+3 + a2 + a1
23*10+3 + a3 + a2 + a1
23*10+3 + a4 + a3 + a2 + a1
分析第一行和第二行可知,递推关系难点1在于如何找到23和3向下传递的传递关系,难点2在于如何找到ai累加关系的实现
脑洞——转化
新的第一列:
23
a1
a2
a3
a4
3
新的第二列:
23*10 + 3
23*10+3 + a1
23*10+3 + a2 + a1
23*10+3 + a3 + a2 + a1
23*10+3 + a4 + a3 + a2 + a1
3
转化关系?
图像来源博客地址——感谢博主
以下为Accepted代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 10000007;
struct Matrix{
LL v[14][14];
};
Matrix multiply(Matrix x, Matrix y, int Matrix_len);
Matrix matrix_pow(Matrix a, int k, int Matrix_len);
int main(){
int n, m, i, j;
Matrix a, b, c;
while(~scanf("%d %d", &n, &m)){
memset(a.v, 0, sizeof(a.v));
memset(b.v, 0, sizeof(b.v));
a.v[0][0] = 23;
for(i = 1; i <= n; i++)
scanf("%lld", &a.v[i][0]);
a.v[n+1][0] = 3;
for(i = 0; i <= n+1; i++){
i != n+1? b.v[i][0] = 10: b.v[i][0] = 0;
b.v[i][n+1] = 1;
}
for(i = 1; i <= n; i++){
for(j = 1; j <= i; j++){
b.v[i][j] = 1;
}
}
c = matrix_pow(b, m, n+2);
a = multiply(c, a, n+2);
printf("%lld\n", a.v[n][0]);
}
return 0;
}
Matrix multiply(Matrix x, Matrix y, int Matrix_len){
Matrix z;
memset(z.v, 0, sizeof(z.v));
for(int i = 0; i < Matrix_len; i++){
for(int j = 0; j < Matrix_len; j++){
for(int k = 0; k < Matrix_len; k++){
z.v[i][j] += x.v[i][k] * y.v[k][j];
z.v[i][j] %= mod;
}
}
}
return z;
}
Matrix matrix_pow(Matrix a, int k, int Matrix_len){
Matrix b;
for(int i = 0; i < Matrix_len; i++){
for(int j = 0; j < Matrix_len; j++){
i == j? b.v[i][j] = 1: b.v[i][j] = 0;
}
}
while(k){
if(k & 1)
b = multiply(b, a, Matrix_len);
a = multiply(a, a, Matrix_len);
k >>= 1;
}
return b;
}
推荐阅读
-
HDU 2256Problem of Precision(矩阵快速幂)
-
POJ3233Matrix Power Series(矩阵快速幂)
-
Recursive sequence(HDU5950 矩阵快速幂)
-
hdu4990——多解矩阵快速幂
-
hdu4990矩阵快速幂
-
HDU4990 Reading comprehension【矩阵快速幂】
-
HDU4990 Reading comprehension【矩阵快速幂】
-
HDU 2256Problem of Precision(矩阵快速幂)
-
hdu 5015 矩阵快速幂
-
矩阵快速幂专题 HDU1757 HDU1575 HDU2604 HDU2256 CF185A HDU2276 HDU2842