[矩阵乘法] PKU3233 Matrix Power Series
[
矩
阵
乘
法
]
M
a
t
r
i
x
P
o
w
e
r
S
e
r
i
e
s
[矩阵乘法]Matrix Power Series
[矩阵乘法]MatrixPowerSeries
Description
Given a
n
×
n
n × n
n×n matrix
A
A
A and a positive integer
k
k
k, find the sum
S
=
A
+
A
2
+
A
3
+
.
.
.
+
A
k
S = A + A^2 + A^3 + ... + A^k
S=A+A2+A3+...+Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integers
n
n
n (
n
n
n ≤
30
30
30),
k
k
k (
k
k
k ≤
1
0
9
10^9
109) and
m
m
m (
m
m
m <
1
0
4
10^4
104). Then follow n lines each containing
n
n
n nonnegative integers below
32
,
768
32,768
32,768, giving
A
A
A’s elements in row-major order.
Output
Output the elements of
S
S
S modulo m in the same way as
A
A
A is given.
Sample Input
2 2 4
0 1
1 1
Sample Output
1 2
2 3
题目解析
为了降低时间复杂度，考虑矩阵乘法
然后可以构造出一个
2
r
2r
2r阶的矩阵
T
T
T
∣
A
E
O
E
∣
\begin{vmatrix} A & E \\ O & E \\ \end{vmatrix}
∣∣∣∣AOEE∣∣∣∣
其中：
A
A
A为输入的矩阵（
A
A
A是
r
r
r阶的矩阵）
O
O
O为全零矩阵 （
O
O
O是值全为
0
0
0的
r
r
r阶矩阵）
E
E
E为对角线矩阵（
E
E
E是除了对角线为
1
1
1，其他的都为
0
0
0的矩阵）
然后可以得出：
∣
S
[
n
−
1
]
,
A
n
∣
=
∣
S
[
n
−
2
]
,
A
n
−
1
∣
∗
T
|S[n-1],A^n| = |S[n-2],A^{n-1}| * T
∣S[n−1],An∣=∣S[n−2],An−1∣∗T
然后通过将矩阵乘法的结合律通过快速幂来计算出
T
n
T^n
Tn再可
A
∗
T
n
A*T^n
A∗Tn来求得答案
关于
T
T
T矩阵的实现
//全零矩阵的实现
//matrix 是已经定义的结构体，n和m是表示矩阵的长和宽，t是矩阵的值
matrix O (int re)
{
matrix c;
c.n = c.m = re;
for (int i = 1; i <= re; ++ i)
for (int j = 1; j <= re; ++ j)
c.t[i][j] = 0;
return c;
}
//对角线矩阵的实现
//matrix 是已经定义的结构体，n和m是表示矩阵的长和宽，t是矩阵的值，O函数为前文定义的全零矩阵
matrix E (int re)
{
matrix c;
c.n = c.m = re;
c = O (re);
for (int i = 1; i <= re; ++ i)
c.t[i][i] = 1;
return a;
}
//关于矩阵的合并。n，m，t，O(),E()前文已述，T1就是前文提到的T矩阵，re为前文提到的r，a是前文提到的A
matrix hb (int re)
{
t1.n = t1.m = re * 2;
for (int i = 1; i <= re; ++ i)
for (int j = 1; j <= re; ++ j)
t1.t[i][j] = a.t[i][j];
matrix er = E (re);
for (int i = 1; i <= re; ++ i)
for (int j = re + 1; j <= re * 2; ++ j)
t1.t[i][j] = er.t[i][j];
for (int i = re + 1; i <= re * 2; ++ i)
for (int j = re + 1; j <= re * 2; ++ j)
t1.t[i][j] = er.t[i][j];
for (int i = re + 1; i <= re * 2; ++ i)
for (int j = 1; j <= re; ++ j)
t1.t[i][j] = 0;
}
最新文章
- 使用shell操作mysql(转)
- MVC4 使用 ckfinder+ckeditor编辑器
- C#各种常用开源框架-支持开源！分享！
- C语言小结之结构类型
- js切换换class
- （原）ubuntu上安装dlib
- WHU1124 Football Match
- OpenCV 学习笔记03 凸包convexHull、道格拉斯-普克算法Douglas-Peucker algorithm、approxPloyDP 函数
- Spark cache、checkpoint机制笔记
- VB中将INT型转换成STRING和从STRING转换成INT型的函数
- Java多线程编程(学习笔记)
- extern、 const、static的理解
- win8开发
- 任务调度框架kunka
- angularJS使用内置服务
- 【Sudoku Solver】cpp
- HDOJ 1085 Holding Bin-Laden Captive!
- GRDB自定义的纯函数
- P2014 选课（树形背包）
- cocoapods学习