[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 D: qwb与神奇的序列 [矩阵]【数学】

# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;
 
# define abs(x) (((x)>0)?(x):-(x))
 
const int N = 3000+10;
const int MOD  = 1e8;
 
const int M = 2;
struct Matrix {
    LL m[M][M];
    void clear0(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=0;
    }
    void clear1(){
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                m[i][j]=(i==j);
    }
    void display(){
        for(int i=0;i<M;i++){
            for(int j=0;j<M;j++)
                printf("%lld ",m[i][j]);
            puts("");
        }
        puts("------");
    }
};
 
Matrix operator * (Matrix &a, Matrix &b){
    Matrix c;c.clear0();
 
    for(int k=0;k<M;k++)
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
 
    return c;
}
 
Matrix operator ^(Matrix &a,LL b){
    Matrix c;c.clear1();
 
    while(b){
        if(b&1) c=c*a;
        b>>=1,a=a*a;
    }
    return c;
}
Matrix a,b;
LL x,y,n;
void solve(){
    a.clear0();b.clear0();
    a.m[0][0]=1,a.m[0][1]=-1;
 
    b.m[0][0]=3,b.m[0][1]=0;
    b.m[1][0]=1,b.m[1][1]=1;
 
    b=b^(n);
    a=a*b;
    printf("%lld\n",a.m[0][0]*(x+y)%MOD);
}
 
int main(){
    while(~scanf("%lld%lld%lld",&x,&y,&n))     solve();
    return 0;
}