【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d828
【解題想法】矩陣快速冪
#include <iostream>
#include <cstring>
using namespace std;
int n, mod = 10000;
struct mat{
int a[2][2];
mat(){
memset(a, 0, sizeof(a));
}
mat operator * (const mat &b)const{
mat ret;
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
for (int k = 0; k < 2; k++){
ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
}
}
}
return ret;
}
};
int main() {
while (cin >> n){
mat ret;
ret.a[0][0] = 1;
ret.a[1][0] = 1;
mat p;
p.a[0][0] = 0;
p.a[0][1] = 1;
p.a[1][0] = 1;
p.a[1][1] = 1;
while (n){
if (n & 1){
ret = p * ret;
}
p = p * p;
n >>= 1;
}
cout << ret.a[0][0] << "\n";
}
}