CodeForces 450B Jzzhu and Sequences

题目链接：http://codeforces.com/problemset/problem/450/B

将题目给出的递推公式稍作变换，

f_n = f_n-1 - f_n-2

化为矩阵形式，用矩阵快速幂运算进行求解。

注意题目直接使用%运算符可能得到负数的结果，对与负数x，x%modnum后，还要将结果加上modnum，这样就能保证结果在0 ~ modnum-1的范围内。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <functional>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define IOS ios_base::sync_with_stdio(false)]
typedef long long LL;
const int INF=0x3f3f3f3f;

const int modnum=1000000007;
const int maxn=3;
typedef struct matrix{
    int v[maxn][maxn];
    void init(){memset(v,0,sizeof(v));}
}M;
inline int mod(LL x){if(x<0) return int(x%modnum+modnum); return int(x%modnum);}
M mul_mod(const M &a,const M &b,int L,int m,int n)
{
    M c; c.init();
    for(int i=0;i<L;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<m;k++)//注意j，k范围
                c.v[i][j]=mod(c.v[i][j]+mod((LL)a.v[i][k]*b.v[k][j]));
        }
    }
    return c;
}
M power(M x,int L,int p)
{
    M tmp; tmp.init();
    for(int i=0;i<L;i++)
        tmp.v[i][i]=1;
    while(p){
        if(p&1) tmp=mul_mod(x,tmp,L,L,L);
        x=mul_mod(x,x,L,L,L);
        p>>=1;
    }
    return tmp;
}

int main()
{
    int x,y,n;
    M a,b;
    while(scanf("%d%d%d",&x,&y,&n)==3){
        x=mod(x); y=mod(y);
        if(n==1){printf("%d
",x); continue;}
        if(n==2){printf("%d
",y); continue;}
        a.init();
        a.v[0][0]=a.v[1][0]=1;
        a.v[0][1]=-1;
        b.init();
        b.v[0][0]=y;
        b.v[1][0]=x;
        a=power(a,2,n-2);
        a=mul_mod(a,b,2,2,1);
        printf("%d
",a.v[0][0]);
    }
}