[Codeforces450B]Jzzhu and Sequences

2014-07-20
竞赛题解 / 模拟
Codeforces

描述 Description

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

$f_{1}=x  f_{2}=y  forall i(i2), f_{i}=f_{i-1}+f_{i+1} $$

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

输入格式 InputFormat

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

输出格式 OutputFormat

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

样例输入 SampleInput

0 -1
2

样例输出 SampleOutput

1000000006

数据范围和注释 Hint

f2 =  - 1;  - 1 modulo (109 + 7) equals (109 + 6).

Codeforces 450B

代码 Code

~~ 矩阵快速幂~~。。。其实是有循环节的，六个 if 就行了。。。C++ 负数的取模运算… 被坑到了。。。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll inf=0x7fffffff;
const ll mod=1000000007;
ll i,j,t,n,m,l,r,k,z,y,x;
inline ll output(ll s)
{
    if (s>0) return s%mod;
    else if (s==0) return 0;
    else return (s%mod+mod)%mod;
}
int main()
{
    scanf("%I64d%I64d",&x,&y);
    scanf("%I64d",&n);
    n=n%6;
    if (n==1) printf("%I64dn",output(x));
    if (n==2) printf("%I64dn",output(y));
    if (n==3) printf("%I64dn",output(y-x));
    if (n==4) printf("%I64dn",output(-x));
    if (n==5) printf("%I64dn",output(-y));
    if (n==0) printf("%I64dn",output(x-y));
    return 0;
}