## 关于kuangbin矩阵专题内题目的小结

1. 矩阵运算的简单优化
2. 取模要求的些许处理
3. 结合矩阵的优化操作
4. 各式各样的构造思路
5. 常常要求的求和操作

### 3.结合矩阵的优化操作

dp问题，有时我们可以发现转移规律具有不变性，同时我们判断出这个单次转移的最远距离可以开矩阵来解决，这样我们就可以使用矩阵快速幂来进行状态转移：【UVA-11651】Krypton Number System

## 【HDU-4686】Arc of Dream【矩阵快速幂】

【HDU-4686】Arc of Dream【矩阵快速幂】

Solution:

$$a_nb_n = AX \times BXa_{n – 1}b_{n – 1} + AX \times BYa_{n – 1} + BX \times AYb_{n – 1} + AY \times BY$$

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const int LIM = 5;
LL n, a0, ax, ay, b0, bx, by;
struct Matrix {
LL v[LIM][LIM];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < LIM; i++)
for (int k = 0; k < LIM; k++)
if (v[i][k])
for (int j = 0; j < LIM; j++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
return ret;
}
};

LL fastPow(LL p, Matrix base) {
Matrix ret = {0};
ret.v[0][0] = a0 * b0 % MOD;
ret.v[1][0] = a0;
ret.v[2][0] = b0;
ret.v[3][0] = 1;
ret.v[4][0] = a0 * b0 % MOD;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret.v[4][0];
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> n >> a0 >> ax >> ay
>> b0 >> bx >> by) {
if (!n) {
cout << 0 << "\n";
continue;
}
ax %= MOD, bx %= MOD, ay %= MOD, by %=MOD, a0 %= MOD, b0 %= MOD;
Matrix base = {ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 0,
0, ax, 0, ay, 0,
0, 0, bx, by, 0,
0, 0, 0, 1, 0,
ax * bx % MOD, ax * by % MOD, ay * bx % MOD, ay * by % MOD, 1};
cout << fastPow(n - 1, base) << "\n";
}
return 0;
}


## 【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

【HDU-4549】M斐波那契数列【数论+矩阵快速幂】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
const LL EXMOD = 1e9 + 6;
const int LIM = 2;
LL a, b, n;

struct Matrix {
LL v[LIM][LIM];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < LIM; i++)
for (int k = 0; k < LIM; k++)
if (v[i][k])
for (int j = 0; j < LIM; j++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j] % EXMOD) % EXMOD;
return ret;
}
};

Matrix fastPow(LL p, Matrix base) {
Matrix ret = {1, 0, 0, 0};
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret;
}

LL fastPow(LL p, LL base) {
LL ret = 1;
while (p) {
if (p & 1) ret = ret * base % MOD;
p >>= 1;
if (p) base = base * base % MOD;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
const Matrix base = {1, 1, 1, 0};
while (cin >> a >> b >> n) {
if (n == 0) cout << a << "\n";
else if (n == 1) cout << b << "\n";
else {
Matrix trans = fastPow(n - 1, base);
cout << fastPow(trans.v[1][0], a) * fastPow(trans.v[0][0], b) % MOD << "\n";
}
}
return 0;
}


## 【UVA-10518】How Many Calls?【矩阵快速幂】

【UVA-10518】How Many Calls?【矩阵快速幂】

Solution:

$$F_0 = 1$$,

$$F_1 = 1$$,

$$F_n = F_{n – 1} + F_{n – 2} + 1$$.

#include <iostream>

using namespace std;

typedef unsigned long long ULL;
ULL n, m;

const int LIM = 3;
struct Matrix {
ULL v[LIM][LIM];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < LIM; i++)
for (int k = 0; k < LIM; k++)
if (v[i][k])
for (int j = 0; j < LIM; j++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % ::m;
return ret;
}
};

ULL fastPow(ULL p, Matrix base) {
Matrix ret = {0};
for (int i = 0; i < LIM; i++) ret.v[i][0] = 1;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret.v[1][0];
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
Matrix base = {1, 1, 1, 1, 0, 0, 0, 0, 1};
for (int k = 1; cin >> n >> m && m; k++) {
cout << "Case " << k << ": " << n << " " << m << " ";
if (n) cout << fastPow(n, base) % m << "\n";
else cout << 1 % m << "\n";
}
return 0;
}


## 【FZU-1911】Construct a Matrix【构造问题】

【FZU-1911】Construct a Matrix【构造问题】

Solution:

import numpy as np
# try to build a valid matrix by using dfs
def dfs(size, crt, ans):
if crt == size * size:
vis = set([])
csum = np.zeros(size, int)
for i in range(size):
rsum = 0
for j in range(size):
rsum = rsum + ans[i * size + j]
csum[j] = csum[j] + ans[i * size + j]
if rsum in vis:
return False
for j in range(size):
if csum[j] in vis:
return False
print("Find one solution!")
print(ans.reshape(size, size))
return True
flag = False
for i in range(-1, 2):
ans[crt] = i
# print("Current : ", ans)
flag = dfs(size, crt + 1, ans) or flag
return flag

size = int(input("The size of matrix to construct:"))
ans = np.zeros(size * size, int);
if not dfs(size, 0, ans):
print("Unfortunately, there are no valid solutions!")
else:
print("All solution have been showed!")

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long LL;
const int LIM = 200 + 10;
int size;
LL n, m;
int ans[LIM * LIM];
int csum[LIM], rsum;

struct Matrix {
LL v[3][3];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < 3; i++)
for (int k = 0; k < 3; k++)
if (v[i][k])
for (int j = 0; j < 3; j++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % ::m;
return ret;
}
};

int fibonacci(LL n, Matrix base) {
Matrix ret = {0};
ret.v[0][0] = ret.v[1][0] = 1;
while (n) {
if (n & 1) ret = base * ret;
n >>= 1;
if (n) base = base * base;
}
return ret.v[2][0];
}

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
int t;
cin >> t;
Matrix base = {1, 1, 0, 1, 0, 0, 0, 1, 1};
for (int k = 1; k <= t; k++) {
cin >> n >> m;
size = fibonacci(n, base);
if (!size || size & 1) {
cout << "Case " << k << ": No" << "\n";
} else {
cout << "Case " << k << ": Yes" << "\n";
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (j) cout << ' ';
if (i == j) cout << (i & 1 ? 0 : -1);
else if (j < i) cout << 1;
else cout << -1;
}
cout << '\n';
}
}
}
return 0;
}


## 【CodeForces-385E】Bear in the Field【矩阵快速幂】

【CodeForces-385E】Bear in the Field【矩阵快速幂】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;

const int SIZE = 6;
LL n, sx, sy, dx, dy, t;
struct Matrix {
LL v[SIZE][SIZE];
Matrix operator * (const Matrix &m) const {
Matrix ret = {0};
for (int i = 0; i < SIZE; i++) {
for (int k = 0; k < SIZE; k++) {
if (v[i][k]) {
for (int j = 0; j < SIZE; j++) {
ret.v[i][j] = ((ret.v[i][j] + v[i][k] * m.v[k][j] % n) + n) % n;
}
}
}
}
return ret;
}
};

Matrix powMod(LL p, Matrix base) {
Matrix ret = {0};
ret.v[0][0] = sx - 1, ret.v[1][0] = sy - 1;
ret.v[2][0] = dx, ret.v[3][0] = dy;
ret.v[4][0] = 1, ret.v[5][0] = 0;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
cin >> n >> sx >> sy >> dx >> dy >> t;
Matrix base = {0};
base.v[0][0] = base.v[0][4] = 2;
base.v[0][1] = base.v[0][2] = base.v[0][5] = 1;
base.v[1][1] = base.v[1][4] = 2;
base.v[1][0] = base.v[1][3] = base.v[1][5] = 1;
base.v[2][0] = base.v[2][1] = base.v[2][2] = base.v[2][5] = 1;
base.v[3][0] = base.v[3][1] = base.v[3][3] = base.v[3][5] = 1;
base.v[2][4] = base.v[3][4] = 2;
base.v[4][4] = 1;
base.v[5][4] = base.v[5][5] = 1;
base = powMod(t, base);
cout << base.v[0][0] + 1 << " " << base.v[1][0] + 1 << "\n";
return 0;
}


## 【CodeForces-392C】Yet Another Number Sequence

【CodeForces-392C】Yet Another Number Sequence

Solution:

#include <iostream>
using namespace std;

typedef long long LL;
const int LIM = 90;
const int SIZE = 50;
const LL MOD = 1e9 + 7;
LL n, C[SIZE][SIZE];
int k;

struct Matrix {
LL v[LIM][LIM];
int size;
Matrix operator * (const Matrix &m) const {
Matrix ret = {{0}};
ret.size = size;
for (int i = 0; i < size; i++)
for (int k = 0; k < size; k++)
if (v[i][k])
for (int j = 0; j < size; j++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j] % MOD) % MOD;
return ret;
}
};

Matrix fastPow(LL p, Matrix base) {
Matrix ret = {{0}};
ret.size = base.size;
for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
while (p) {
if (p & 1) ret = base * ret;
p >>= 1;
if (p) base = base * base;
}
return ret;
}

void buildC() {
for (int i = 0; i <= k; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}

int main(void) {
scanf("%lld%d", &n, &k);
buildC();
Matrix base = {{0}};
base.size = (k + 1) * 2 + 1;
for (int i = 0; i <= k; i++)
for (int j = 0; j <= i; j++)
base.v[i][j] = base.v[i][j + k + 1] = base.v[i + k + 1][j] = C[i][j];
base.v[base.size - 1][base.size - 1] = base.v[base.size - 1][k] = 1;
base = fastPow(n, base);
LL ans = 0;
for (int i = 0; i < base.size - 1; i++)
ans = (ans + base.v[base.size - 1][i]) % MOD;
printf("%lld\n", ans);
return 0;
}


## 【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

【HDU-4565】So Easy!【矩阵快速幂+向上取整的处理】

Solution：

#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
LL MOD, a, b;
struct Matrix {
LL v[2][2];
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
return ret;
}
};

Matrix fastPow(int p, Matrix base) {
Matrix ret = {a, 0, 1, 0};
while (p) {
if (p & 1) ret = base * ret;
base = base * base;
p >>= 1;
}
return ret;
}

int main(void) {
int n;
while (~scanf("%lld%lld%d%lld", &a, &b, &n, &MOD)) {
Matrix base = {a, b, 1, a};
base = fastPow(n - 1, base);
printf("%lld\n", base.v[0][0] * 2 % MOD);
}
return 0;
}


## 【UVA-10870】Recurrences【矩阵快速幂】

【UVA-10870】Recurrences【矩阵快速幂】

Solution:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int MOD = 0;
const int LIM = 20;
struct Matrix {
LL v[LIM][LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
ret.size = size;
for (int i = 0; i < size; i++) {
for (int k = 0; k < size; k++) {
if (v[i][k])
for (int j = 0; j < size; j++) {
ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
}
}
}
return ret;
}
};

Matrix fastPow(int p, Matrix m) {
Matrix ret = {0};
ret.size = m.size;
for(int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
while (p) {
if (p & 1) ret = ret * m;
m = m * m;
p >>= 1;
}
return ret;
}

LL input[LIM], output[LIM];
Matrix base;

int main() {
int d, n;
while (~scanf("%d%d%d", &d, &n, &MOD) && (d || n) && MOD) {
memset(&base, 0, sizeof base);
base.size = d;
for (int i = 0; i < d; i++)
scanf("%lld", &base.v[0][i]), base.v[0][i] %= MOD;
for (int i = 1; i < d; i++)
base.v[i][i - 1] = 1;
for (int i = 0; i < d; i++)
scanf("%lld", &input[d - 1 - i]), input[d - 1 - i] %= MOD;
if (n <= d) printf("%lld\n", input[d - n]);
else {
base = fastPow(n - d, base);
LL ans = 0;
for (int i = 0; i < d; i++) {
ans = (ans + base.v[0][i] * input[i]) % MOD;
}
printf("%lld\n", ans);
}
}
return 0;
}


## 【UVA-1386】Cellular Automaton【循环矩阵的矩阵快速幂】

【UVA-1386】Cellular Automaton【循环矩阵的矩阵快速幂】

Solution:

#include <iostream>

using namespace std;

struct Matrix {
int v[10];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}};
ret.size = size;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
ret.v[i] += v[j] * m.v[(size - i + j) % size];
}
}
return ret;
}
};

Matrix fastPow(int k, Matrix m) {
Matrix ret = {{0}};
ret.size = m.size;
ret.v[0] = 1;
while (k) {
if (k & 1) ret = ret * m;
if (k) m = m * m;
k >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
// cin.tie(NULL);
int n, k;
while (cin >> n && n) {
Matrix input;
input.size = n;
for (int i = 0; i < n; i++)
cin >> input.v[i];
while (cin >> k && k) {
Matrix output = fastPow(k, input);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j) cout << ' ';
cout << output.v[(n - i + j) % n];
}
cout << endl;
}
}
}
return 0;
}


#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
int n, mod, d, k;
const int LIM = 500 + 10;
struct Matrix {
LL v[LIM];
int size;
Matrix operator * (const Matrix & m) const {
Matrix ret = {{0}};
ret.size = size;
for (int i = 0; i < size; i++) {
for (int k = 0; k < size; k++) {
ret.v[i] = (ret.v[i] + v[k] * m.v[(size - i + k) % size]) % mod;
}
}
return ret;
}
};
Matrix build() {
Matrix ret = {{0}};
ret.size = n;
for (int i = 0; i <= d; i++)
ret.v[i] = ret.v[(n - i) % n] = 1;
return ret;
}
Matrix fastPow(int p, Matrix m) {
Matrix ret = {{0}};
ret.size = m.size;
ret.v[0] = 1;
while (p) {
if (p & 1) ret = ret * m;
p >>= 1;
if (p) m = m * m;
}
return ret;
}
LL input[LIM], output[LIM];

int main() {
while (~scanf("%d%d%d%d", &n, &mod, &d, &k)) {
memset(output, 0, sizeof output);
for (int i = 0; i < n; i++)
scanf("%d", &input[i]);
Matrix trans = build();
trans = fastPow(k, trans);
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) {
output[i] = (output[i] + trans.v[(n - i + k) % n] * input[k]) % mod;
}
}
for (int i = 0; i < n; i++) {
if (i) putchar(' ');
printf("%d", output[i]);
}
putchar('\n');
}
return 0;
}