【2021】阿里巴巴编程题（4星）第2题

#include <iostream>

using namespace std;
typedef long long LL;
LL mod = 1e9+7;

int main()
{
    int T = 0;
    cin >> T;
    while(T--){
        int a=0,b=0,n=0;
        cin >> a >> b >> n;
        LL res=0;
        //a^k+1 + b^k+1 = (a^k + b^k)(a+b) - ab(a^k-1 + b^k-1)
        LL k_befor = 2;
        LL k_bb = 0;
        for (int i = 1; i <= n; i++)
        {
            if(i==1)
            {
                res = a;
                k_bb = k_befor;
                k_befor = res;
                continue;
            }
            res = ((a*k_befor-b*k_bb)+mod)%mod;
            k_bb = k_befor;
            k_befor = res;
        }
        res = (res+mod)%mod;
        cout << res << endl;
    }
    return 0;
}