第二场（A2-牛牛的Fib序列）

链接：https://ac.nowcoder.com/acm/contest/6357/A
来源：牛客网

题目描述：
牛牛重新定义了斐波那契数列，牛牛定义f(n) = f(n-1)+f(n+1); f(1)=a, f(2)=b， 现在给定初始值 a, b，现在求第n项f(n)%1000000007的值。
其中 1<=|x|, |y|, n<=10^9
备注:
最终的答案应是一个非负整数，如-1 % 1000000007 = 1000000006
解题思路：
根据f(n)=f(n-1)+f(n+1)，有f(n+1)=f(n)-f(n-1)。假设f1=a，f2=b，找规律：
f1=a, f2=b, f3=b-a, f4=-a, f5=-b, f6=a-b, f7=a, f8=b, ...
可以看到数组每6个元素循环一次。那么我们只需要计算n在循环节的哪个位置即可，时间复杂度O(1)。注意返回结果非负。
代码：

class Solution {
public:
    /**
     * 
     * @param a int整型 
     * @param b int整型 
     * @param n int整型 
     * @return int整型
     */
    int solve(int a, int b, int n) {
        // write code here
        // f1 = a, f2 = b, f3 = b - a, f4 = -a, f5 = -b, f6 = a - b
        int m = 1e9 + 7;
        a = (a + m) % m;
        b = (b + m) % m;
        if(n == 1) return a;
        if(n == 2) return b;
        int f[] = {a, b, (b - a + m) % m, (-a + m) % m, (-b + m) % m, (a - b + m) % m};
        return f[(n + 5) % 6];
    }
};