poj 3070(矩阵快速幂)

poj 3070

求Fibonacci数列，但是这里直接递推肯定炸。
我们根据
$$F_{n} = F_{n-1} +F_{n-2}$$
构造矩阵
$$
\begin{pmatrix}
1 & 1 \\\
1 & 0
\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1}
\end{pmatrix}
$$
矩阵快速幂即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 4, MO = 10000;
int n;
struct matrix {
    int x, y, ma[MAXN][MAXN];
    void init(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = (i==j);}//初始化为单位矩阵
    void init2(int x, int y) {this->x = x, this->y = y; for (int i=0;i<MAXN;i++) for (int j=0;j<MAXN;j++) ma[i][j] = 0;}//初始化为空矩阵
}a;
matrix mul(matrix ai, matrix bi) {//矩阵乘法 
    matrix ret; 
    ret.init2(2, 2);
    for (int i=0;i<ai.x;i++) {
        for (int j=0;j<bi.y;j++) {
            for (int k=0;k<ai.y;k++) {
                ret.ma[i][j] = (ret.ma[i][j]%MO + (ai.ma[i][k]%MO) * (bi.ma[k][j]%MO))%MO;
            }
        }
    }
    return ret;
}
matrix poww(matrix ai, int x) {//快速幂 
    matrix s, ret; 
    s = ai, ret.init(2, 2);
    while (x) {
        if (x&1) ret = mul(ret, s);
        s = mul(s, s);
        x>>=1;
    }
    return ret;
}
void clean() {}
void solve() {
    clean();
    if (n==0) {printf("0\n"); return ;}
    if (n==1||n==2) {printf("1\n"); return ;}
    a.init(2,2), a.ma[0][0] = 1, a.ma[0][1] = 1, a.ma[1][0] = 1, a.ma[1][1] = 0;//矩阵初始化 
    matrix b = poww(a, n-1);
    printf("%d\n", b.ma[0][0]);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1&&n!=-1) solve();
    return 0;
}