最近被一道题给坑了很久

题目如下

题目描述

斐波那契数列我们非常熟悉，同时斐波那契数列有如下的推广形式：

f[1] = x , f[2] = y, 对于n>3 ,f[n] = f[n-1] + f[n+1].

现在给出整数n,请输出f[n]%(1e9 + 7).

输入

第一行输入一个整数T，表示测试的样例数。

下面T组输入，每组输入两行，第一行是整数x，y(x∈[1,1000000000] , y∈[1,1000000000])

第二行是整数n(n∈[1,1000000000])

输出

按照题目要求输出。

样例输入

1
1 2
1

样例输出

1

本题的解决办法是找出规律，不要死磕n>3这个条件，找出规律后

即周期为6

a[3] = a[9] 

a[4] = a[10]

...

且半周期的数互为相反数

故a[3] = -a[6]

a[4] = -a[7]

...

所以由此规律推出

        a[1] = x, a[2] = y; 
        a[4] = -a[1], a[5] = -a[2], 
        a[3] = a[4] - a[5], a[6] = x-y;

之后就可以模6输出了

故数组只要开7就够了

但是你会发现前6个中有负数

而%的结果是不能有负数的

故我们通过加mod后取模输出保证正数

代码如下：

#include<stdio.h>
const int mod = 1e9+7;
typedef long long ll;
ll a[10];
ll n, x, y;
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%lld %lld", &x, &y);
        scanf("%lld", &n);
        a[1] = x, a[2] = y; 
        a[4] = -a[1], a[5] = -a[2], 
        a[3] = a[4] - a[5], a[6] = x-y;
        printf("%lld\n", (a[(n-1)%6 + 1]%mod+mod)%mod); 
        /*
        此处的两个重点：
		1.数组下标，由于6的时候%6为0，而a[0]并无数据，所以采取(n-1)%6+1
		2.先对a[(n-1)%6+1]取模，结果可能是负数，故我们继续加上mod保证正数后再取模。这时的结果必为正数。 
		*/ 
    }
    return 0;
}