## 【UVA-11149】Power of Matrix【矩阵快速幂】

【UVA-11149】Power of Matrix【矩阵快速幂】

Solution：

$$A + A^2 + A^3 + … + A^k = (A + A^2 + … + A^{k / 2})(E + A^{k / 2})$$

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

using namespace std;

const int MOD = 10;
const int LIM = 40 + 10;
struct Matrix {
int 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 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][j] = (v[i][j] + m.v[i][j]) % MOD;
return ret;
}
};
int n;
Matrix iden, base;

inline void init() {
memset(&iden, 0, sizeof iden);
for (int i = 0; i < n; i++) iden.v[i][i] = 1;
iden.size = n;
memset(&base, 0, sizeof base);
base.size = n;
}

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;
if (p) m = m * m;
p >>= 1;
}
return ret;
}

Matrix binarySum(int k) {
if (k == 1) return base;
else if (k & 1) return binarySum(k >> 1) * (iden + fastPow(k >> 1, base)) + fastPow(k, base);
else return binarySum(k >> 1) * (iden + fastPow(k >> 1, base));
}

int main() {
int k;
while (~scanf("%d", &n) && n) {
scanf("%d", &k);
init();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &base.v[i][j]);
base.v[i][j] %= MOD;
}
Matrix ans = binarySum(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j) putchar(' ');
printf("%d", ans.v[i][j]);
}
putchar('\n');
}
putchar('\n');
}
return 0;
}


## 【UVA – 10689】Yet another Number Sequence

【UVA – 10689】Yet another Number Sequence

Solution:

em…不用多想，就是个用矩阵快速幂求第n项。

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

using namespace std;

int MOD = 0;
const int LIM = 2;
struct Matrix {
int 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;
}
};

const Matrix BASE = {1, 1, 1, 0};

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

int main() {
int t;
scanf("%d",&t);
int a, b, n, m;
while (t--) {
scanf("%d%d%d%d", &a, &b, &n, &m);
MOD = 1;
while (m--) MOD *= 10;
if (n == 0) printf("%d\n", a);
else if (n == 1) printf("%d\n", b);
else {
Matrix trans = fastPow(n - 1, BASE);
printf("%d\n", (b * trans.v[0][0] + a * trans.v[0][1]) % MOD);
}
}
return 0;
}


## 【UVA-11551】Experienced Endeavour【矩阵快速幂】

【UVA-11551】Experienced Endeavour【矩阵快速幂】

Solution:

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

using namespace std;

const int MOD = 1000;
const int LIM = 50 + 10;
struct Matrix {
int 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;
}
};
int a[LIM], ans[LIM], n;

inline void init() {
memset(ans, 0, sizeof ans);
}

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;
if (p) m = m * m;
p >>= 1;
}
return ret;
}

int main() {
int t;
scanf("%d",&t);
int r, x, b;
while (t--) {
init();
scanf("%d%d", &n, &r);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
Matrix base = {{0}};
base.size = n;
for(int i = 0 ; i < n; i++) {
scanf("%d", &x);
for(int j = 0 ; j < x; j++) {
scanf("%d", &b);
base.v[i][b] = 1;
}
}
base = fastPow(r, base);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
ans[i] = (ans[i] + a[j] * base.v[i][j]) % MOD;
for(int i = 0; i < n; i++) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
putchar('\n');
}
return 0;
}


## 【HDU-4965】Fast Matrix Calculation

【HDU-4965】Fast Matrix Calculation

Solution:

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000 + 10;
const int K = 6 + 2;
const int MOD = 6;
struct Matrix {
int v[K][K];
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;
}
} c;
int a[N][K], b[K][N];
long long tmp[N][K], ans[N][N];
int n, k;

Matrix build() {
Matrix ret = {{0}};
ret.size = k;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
for (int w = 0; w < n; w++) {
ret.v[i][j] = (ret.v[i][j] + b[i][w] * a[w][j]) % MOD;
}
}
}
return ret;
}

Matrix powMod(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 = m * ret;
if (p) m = m * m;
p >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
while (cin >> n >> k && n && k) {
memset(tmp, 0, sizeof tmp);
memset(ans, 0, sizeof ans);
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++)
cin >> a[i][j];
for (int i = 0; i < k; i++)
for (int j = 0; j < n; j++)
cin >> b[i][j];
Matrix c = build();
c = powMod(n * n - 1, c);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
for (int w = 0; w < k; w++) {
tmp[i][j] = (tmp[i][j] + a[i][w] * c.v[w][j]) % MOD;
}
}
}
long long sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int w = 0; w < k; w++) {
ans[i][j] = (ans[i][j] + tmp[i][w] * b[w][j]) % MOD;
}
sum += ans[i][j];
}
}
cout << sum << endl;
}
return 0;
}


## 【UVA-11651】Krypton Number System

【UVA-11651】Krypton Number System

Solution:

$$dp[i][k] = \sum dp[i – (j – k)^2][j]$$

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const LL MOD = 1ll << 32;
const int LIM = 250;
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;
}
};
int b;
LL s, ans;
LL dp[LIM][LIM];

inline void init() {
memset(dp, 0, sizeof dp);
ans = 0;
int lim = (b - 1) * (b - 1);
for (int j = 1; j < b; j++) dp[0][j] = 1;
for (int i = 0; i <= lim; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < b; k++) {
if (j == k) continue;
int tmp = (j - k) * (j - k);
if (i + tmp > lim) continue;
dp[i + tmp][k] += dp[i][j];
}
}
}
}

Matrix buildBase() {
Matrix ret = {{0}};
ret.size = (b - 1) * (b - 1) * b;
LL tmp;
for (int i = 0; i <= ret.size - b; i++)
ret.v[i][i + b] = 1;
int lim = (b - 1) * (b - 1);
for (int i = 0; i < lim; i++) {
for (int j = 0; j < b; j++) {
for (int k = 0; k < b; k++) {
if (j == k) continue;
tmp = i + (k - j) * (k - j);
if (tmp == lim) ret.v[(tmp - 1) * b + k][i * b + j] = 1;
}
}
}
return ret;
}

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

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for (int k = 1; k <= t; k++) {
cin >> b >> s;
init();
int lim = (b - 1) * (b - 1);
if (s <= lim) {
for (int j = 0; j < b; j++) ans += dp[s][j];
cout << "Case " << k << ": " << ans << "\n";
} else {
Matrix base = buildBase();
int size = lim * b;
int pos = (lim - 1) * b;
base = powMod(s - lim, base);
for (int j = 0; j < b; j++) {
LL tmp = 0;
for (int k = 0; k < size; k++)
tmp = (tmp + base.v[pos + j][k] * dp[k / b + 1][k % b]) % MOD;
ans = (ans + tmp + MOD) % MOD;
}
cout << "Case " << k << ": " << ans << "\n";
}
}
return 0;
}


Solution:

Part 1.当k是偶数时，则$$a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1$$。

Part 2.当k是奇数时，则$$a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1$$。

#include <iostream>

using namespace std;

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

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n;
while (cin >> n >> MOD) {
if (n == 1) cout << 1 % MOD << "\n";
else if (n == 2) cout << 2 % MOD << "\n";
else {
Matrix trans = powMod(n - 2, BASE);
LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
cout << ans << "\n";
}
}
return 0;
}


## 【HDU-5015】233 Matrix【矩阵快速幂】

【HDU-5015】233 Matrix【矩阵快速幂】

Solution：

1.发现可以通过每一列的值推出下一列的值。

2.注意到0没有贡献于最终结果，是题设故意设计的一个坑。

#include <iostream>

using namespace std;

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

Matrix buildBase(int size) {
Matrix ret = {{0}, size};
ret.t[size - 1][size - 1] = 1;
for (int i = size - 2; i >= 0; i--) {
ret.t[i][0] = 10;
ret.t[i][size - 1] = 1;
for (int j = 1; j <= i; j++)
ret.t[i][j] = 1;
}
return ret;
}

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

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n, m;
LL ori[LIM];
while (cin >> n >> m) {
ori[0] = 23;
ori[n + 1] = 3;
for (int i = 1; i <= n; i++) cin >> ori[i];
if (m == 0) cout << ori[n] << "\n";
else {
Matrix trans = powMod(m, buildBase(n + 2));
LL ans = 0;
for (int i = 0; i <= n + 1; i++)
ans = (ans + trans.t[n][i] * ori[i]) % MOD;
cout << ans << "\n";
}
}
return 0;
}


## 【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】

【CodeForces-450B】Jzzhu and Sequences【矩阵快速幂】

Solution:

#include <iostream>

using namespace std;

typedef long long LL;
const LL MOD = 1e9 + 7;
struct Matrix {
LL t[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.t[i][j] = ((ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD + MOD) % MOD;
}
}
}
return ret;
}
};

const Matrix BASE = {{1, -1, 1, 0}};

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{1, 0, 0, 1}};
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL x, y, n;
while (cin >> x >> y >> n) {
if (n == 1) cout << (x + MOD) % MOD << "\n";
else if (n == 2) cout << (y + MOD) % MOD << "\n";
else {
Matrix trans = powMod(n - 2, BASE);
cout << ((trans.t[0][0] * y + trans.t[0][1] * x) % MOD + MOD) % MOD << "\n";
}
}
return 0;
}