锐客网

  1. 首页 > it技术 > >

CodeForces - 450B Jzzhu and Sequences 规律

数学

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).
Examples
Input

2 3 3

Output
1

Input
0 -1 2

Output
1000000006

【CodeForces - 450B Jzzhu and Sequences 规律】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).
题意：给定序列f[1] = x, f[2] = y,f[i] = f[i + 1] + f[i - 1]，求 f[n]
题解：f[i] = f[i - 1] - f[i - 2]先别着急矩阵快速幂啊 写几个看看
abb-a-a-b-b+aab这不就6个一循环了嘛，注意取模就行了
#include using namespace std; const int mod=1e9+7; int a[15]; int n; int main() { while(~scanf("%d%d",&a[1],&a[2])) { a[1]=(a[1]%mod+mod)%mod; a[2]=(a[2]%mod+mod)%mod; for(int i=3; i<=6; i++) { a[i]=((a[i-1]-a[i-2])%mod+mod)%mod; } scanf("%d",&n); n%=6; if(n==0) n=6; cout<


    推荐阅读


    上一篇：CodeForces - 245C Game with Coins

    下一篇：Android|Android 系统页面的调用