## 【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;
}
```