Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

Matrix Power Series

Posted on In , ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

来源POJ第3233题Matrix Power Series

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given.

Sample Input

1
2
3
2 2 4
0 1
1 1

Sample Output

1
2
1 2
2 3

题目要求的是 A+A2+…+Ak，而不是单个矩阵的幂

　　那么我们可以构造一个分块的辅助矩阵 S，其中 A 为原矩阵，E 为单位矩阵，O 为0矩阵

　　img

　　我们将 S 取幂，会发现一个特性

　　img

　　Sk 右上角那一块不正是我们要求的 A+A2+…+Ak 吗？

　　于是我们构造出 S 矩阵，然后对它求矩阵快速幂即可，最后别忘了减去一个单位阵

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
import java.util.*;

public class Main {

	 static int n;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();  //n阶矩阵
		int k = in.nextInt();  //k次幂
		int m = in.nextInt();  //mod m

		int [][] matrix = new int[2*n][2*n];
		int [][] ans = new int[n][n];
		int sum = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) {
				matrix[i][j] = in.nextInt();
				//ans[i][j] = matrix[i][j] % m;
			}
		//构造右边的单位矩阵
		for(int i = 0 ; i < n ; i++)
			for(int j = n ; j < 2*n; j++)
				if(j - i == n)
					matrix[i][j] = 1;
				//构造右下方单位矩阵
		for(int i = n; i < 2*n; i++)
			for(int j = n ; j < 2*n ; j++)
				if(i == j)
					matrix[i][j] = 1;

				n <<= 1;
				matrix = pow(matrix,k + 1,m);
				n >>= 1;

				//减去一个单位矩阵
			for(int i = 0 ; i < n ; i++) {
				for (int j = n; j < 2*n; j++) {
					if(j - i == n)
						matrix[i][j] = (matrix[i][j] - 1 + m) % m;
					if(j == 2*n - 1)
					System.out.println(matrix[i][j]);
					else
						System.out.print(matrix[i][j] + " ");
				}
			}

	}

	//矩阵乘法
	public static int[][] matrixMul(int [][] a, int [][]b,int mod){
		int [][] ans = new int[a.length][a.length];
		for(int i = 0;i < n; i++)
			for(int j = 0; j < n; j++){
				for(int k = 0 ; k < n ; k++){
					ans[i][j] += a[i][k] * b[k][j];
					ans[i][j] %= mod;
				}
			}
		return ans;
	}

	//矩阵加法
	public static  void add(int [][]a,int [][]b,int mod){
		for(int i = 0 ; i < a.length ; i++)
			for(int j = 0 ; j < a.length ; j++){
				a[i][j] += b[i][j];
				a[i][j] %= mod;
			}
	}

	//矩阵快速幂
	public static int[][] pow(int [][] a,int n,int mod){
		int [][] ans = new int[a.length][a.length];
		for(int i = 0 ; i < a.length / 2; i++)
			for(int j = 0 ; j < a.length / 2; j++)
				if(i == j)
					ans[i][j] = 1;

		while (n != 0){
			if((n & 1) == 1)
				ans = matrixMul(ans,a,mod);
			a = matrixMul(a,a,mod);
			n >>= 1;
		}
		return ans;
	}
}