UVA 10229 Modular Fibonacci

斐波那契取MOD。利用矩阵快速幂取模

http://www.cnblogs.com/Commence/p/3976132.html

代码：

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

struct node

{

    LL mat[][];

}ans,t;

LL MOD,N;

int M;

void init()

{

    ans.mat[][]=;ans.mat[][]=;ans.mat[][]=;ans.mat[][]=;

    t.mat[][]=;t.mat[][]=;t.mat[][]=;t.mat[][]=;

    MOD=<<M;

}

node mult(node a,node b)

{

    node res;

    for (int i=;i<;i++)

        for (int j=;j<;j++)

        res.mat[i][j]=(a.mat[i][]*b.mat[][j]+a.mat[i][]*b.mat[][j])%MOD;

    return res;

}

int main()

{

    while (scanf("%lld %d",&N,&M)!=EOF)

    {

        init();

        //printf("%lld\n",MOD);

        while (N)

        {

            if (N&) ans=mult(ans,t);

            t=mult(t,t);

            N>>=;

        }

        //printf("%lld %lld %lld %lld\n",ans.mat[0][0],ans.mat[0][1],ans.mat[1][0],ans.mat[1][1]);

        printf("%lld\n",(ans.mat[][])%MOD);

    }

    return ;

}