白告山风

不定期更新摄影，acm题解等等有趣的东西~

0%

矩阵快速幂专题

发表于 更新于 分类于
本文字数： 7.2k 阅读时长 ≈ 7 分钟

例题1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。

Input
数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。

Output
对应每组数据，输出Tr(A^k)%9973。

输入样例
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
输出样例
2
2686
源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
long long a[11][11];
const int mod=9973;
void mul(long long (*a1)[11],long long (*a2)[11],int k){//矩阵乘法  k为矩阵的阶数 
	long long remain[11][11]={0} ;
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int z=1;z<=k;z++){
				remain[i][j]+=(a1[i][z]*a2[z][j])%mod;//矩阵乘法的核心
			}
		} 
	} 
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			a1[i][j]=remain[i][j];
		}
	}
}
void quick_mi(int k,int len){//k为幂，len为阶 
	long long remain[11][11]={0};
	for(int i=1;i<=len;i++){
		remain[i][i]=1;
	}
	while(k){//和一般快速幂一样
		if(k&1)mul(remain,a,len);
		mul(a,a,len);
		k>>=1;
	}
	for(int i=1;i<=len;i++){
		for(int j=1;j<=len;j++){
			a[i][j]=remain[i][j];
		}
	}
}

int main(){
	int t=0;
	scanf("%d",&t);
	while(t--){
		int n,k,ans=0;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&a[i][j]);
			}
		}
		quick_mi(k,n);
		for(int i=1;i<=n;i++){
			ans+=a[i][i];
			if(ans>=mod){
				ans%=mod;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

​ 这道题还比较基础，仅仅考验了矩阵运算和快速幂的部分，核心的将题目递推公式推出然后矩阵乘法化还没有考察到，但接下来的第二题便有所体现了。

例题2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Problem Description
Everybody knows Fibonacci numbers, now we are talking about the Tribonacci numbers:
T[0] = T[1] = T[2] = 1;
T[n] = T[n - 1] + T[n - 2] + T[n - 3] (n >= 3)

Given a and b, you are asked to calculate the sum from the ath Fibonacci number to the bth Fibonacci number, mod 1,000,000,007, that is (T[a] + T[a + 1] + … + T[b]) % 1,000,000,007.

Input
There are multiple cases (no more than 100).

Each case contain two non-negative integers a b(a <= b and a, b < 1,000,000,000)

Output
For each case, output the sum % 1,000,000,007.

输入样例
0 2
0 5
输出样例
3
20

题目大意是我们现在重新定义一个数列规律，求第a项到第b项之和。

源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long b[5][5];
long long f[5]={0,3,1,1,1};//这里是矩阵化的数组的初始状态
int a,b1;
void init_mat(){//初始化矩阵乘法运算数组b
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			if(i==1){
				b[i][j]=1;
			}
			else if(i==2){
				if(j==1){
					b[i][j]=0;
				}
				else{
					b[i][j]=1;
				}
			}
			else {
				if(i-1==j){
					b[i][j]=1;
				}
				else{
					b[i][j]=0;
				}
			} 
		}
	}
}
void mul(long long (*a)[5],long long (*a1)[5]){//矩阵乘法
	long long remain[5][5]={0};
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			for(int z=1;z<=4;z++){
				remain[i][j]=(remain[i][j]+a[i][z]*a1[z][j])%mod;
			}
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			a[i][j]=remain[i][j];
		}
	}
}
void quick_mi(int k){//快速幂
	long long remain[5][5]={0};
	for(int i=1;i<=4;i++){
		remain[i][i]=1;
	}
	while(k){
		if(k&1)mul(remain,b);
		mul(b,b);
		k>>=1; 
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			b[i][j]=remain[i][j];
		}
	}
}
int count(int k){
	if(k<0){
		return 0;
	}
	else if(k<3){
		return k+1;
	}
	else{
		long long ans=0;
		quick_mi(k-2);
		for(int i=1;i<=4;i++){
			ans+=b[1][i]*f[i];
			if(ans>=mod)ans%=mod;
		}
		return ans;
		
	}
}
int main(){
	while(scanf("%d%d",&a,&b1)==2){
		init_mat();
		int ans1=count(a-1);
		init_mat();
		int ans2=count(b1);
		printf("%d\n",(ans2-ans1+mod)%mod);//ans2原值对mod的余数可能会小于ans1，所以要进行取余操作 易错点！！！ 
	}
	return 0;
}

这道题虽然给出了我们到第几项的规律，但是需要求的是sum，所以我们还需要推出前缀和的原公式，然后再进行矩阵快速幂。

例题3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Problem Description
As we all known , the Fibonacci series : F(0) = 1, F(1) = 1, F(N) = F(N - 1) + F(N - 2) (N >= 2).Now we define another kind of Fibonacci : A(0) = 1 , A(1) = 1 , A(N) = X A(N - 1) + Y A(N - 2) (N >= 2).And we want to Calculate S(N) , S(N) = A(0)^2 +A(1)^2+……+A(n)^2.

Input
There are several test cases.
Each test case will contain three integers , N, X , Y .
N : 2<= N <= 2^31 – 1
X : 2<= X <= 2^31– 1
Y : 2<= Y <= 2^31 – 1

Output
For each test case , output the answer of S(n).If the answer is too big , divide it by 10007 and give me the reminder.
输入样例
2 1 1 
3 2 3 
输出样例
6
196

源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
long long n,x,y;
long long f[4]={2,1,1,1};
long long b[4][4]={0};
void init_mat(){
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(i==0){
				b[i][0]=1;
				b[i][1]=x*x%mod;
				b[i][2]=2*x*y%mod;
				b[i][3]=y*y%mod;
			}
			else if(i==1){
				b[i][0]=0;
				b[i][1]=x*x%mod;
				b[i][2]=2*x*y%mod;//防止longlong溢出  原因是longlong的最大值是20左右，x，y最大值为1<<31-1 如果 2xy*2xy容易向上溢出 .
				b[i][3]=y*y%mod;
			}
			else if(i==2){
				b[i][0]=0;
				b[i][1]=x;
				b[i][2]=y;
				b[i][3]=0;
			}
			else{
				b[i][0]=0;
				b[i][1]=1;
				b[i][2]=0;
				b[i][3]=0;
			}
		}
	}
}
void mul(long long (*a)[4],long long (*a1)[4]){
	long long remain[4][4]={0};
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			for(int z=0;z<4;z++){
				remain[i][j]=(remain[i][j]+a[i][z]*a1[z][j])%mod;
			}
		}
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			a[i][j]=remain[i][j];
		}
	}
}
void quick_mi(int k){
	long long remain[4][4]={0};
	for(int i=0;i<4;i++){
		remain[i][i]=1;
	} 
	while(k){
		if(k&1)mul(remain,b);
		mul(b,b);
		k>>=1;
	} 
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			b[i][j]=remain[i][j];
		}
	}
}
int main(){
	while(scanf("%lld%lld%lld",&n,&x,&y)==3){
		if(x>=mod){
			x%=mod;
		}
		if(y>=mod){
			y%=mod;
		}
		if(n<2){
			if(n==0)printf("1\n");
			else if(n==1)printf("2\n");
		}
		init_mat();
		quick_mi(n-1);
		long long ans=0;
		for(int i=0;i<4;i++){
			ans+=f[i]*b[0][i];
			if(ans>=mod)ans%=mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}

这篇博客仅仅还是一篇草稿，温故而知新，还需要后期的复习后的感想，才算发挥出来这篇博客应有的作用。