CodeforcesRound#258(Div.2)B.JzzhuandSequences（矩阵快速幂）_html/css_WEB-ITnose

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

----------------------------------------------------------------------------------------------------------------------------------------------------------

欢迎光临天资小屋：http://user.qzone.qq.com/593830943/main

----------------------------------------------------------------------------------------------------------------------------------------------------------

B. Jzzhu and Sequences

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Jzzhu has invented a kind of sequences, they meet the following property:

You are given x and y, please calculate fn modulo 1000000007 (109?+?7).

Input

The first line contains two integers x and y (|x|,?|y|?≤?109). The second line contains a single integer n (1?≤?n?≤?2·109).

Output

Output a single integer representing fn modulo 1000000007 (109?+?7).

Sample test(s)

input

2 33

output

input

0 -12

output

1000000006

Note

In the first sample, f2?=?f1?+?f3, 3?=?2?+?f3, f3?=?1.

In the second sample, f2?=??-?1; ?-?1 modulo (109?+?7) equals (109?+?6).

代码如下：

#include #include #include using namespace std;struct A{    int mat[2][2];};A d,f;__int64 n,mod;A mul(A a,A b){    A t;    memset(t.mat,0,sizeof(t.mat));    for(int i=0;i>= 1 ;    }    return m;}int main(){    n=2;    int k,t;__int64 x,y,z;    while(scanf("%I64d%I64d",&x,&y)!=EOF)    {        int s=0;        scanf("%I64d",&z);        mod=1000000007;        if(z == 1)        {            if(x < 0)                printf("%I64d\n",x+mod);            else                printf("%I64d\n",x);            continue;        }        d.mat[0][1]=-1;d.mat[1][1] = 0;        d.mat[0][0]=d.mat[1][0]=1;        A ret=quickP(z-2);//z-2 乘的次数        __int64 ans=(ret.mat[0][0]*y%mod+ret.mat[0][1]*x%mod)%mod;        if(ans < 0)            ans+=mod;        printf("%I64d\n",ans);    }    return 0;}