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