http://www.lightoj.com/volume_showproblem.php?problem=1070

思路：\({(a+b)}^n =(a+b){(a+b)}^{n-1} \) \((ab)C_{n}^{r}a^{n-r}b{r} = C_{n+2}^{r}a^{n-r+2}b{r} - a^{n+2} - b^{n+2} \)

综上\( f(n) = (a+b)f(n-1)-(ab)f(n-2) \)

/** @Date    : 2016-12-19-19.53  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version :  */#include<bits/stdc++.h>#define LL long long#define PII pair#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;typedef unsigned long long ull;struct matrix{    ull mt[2][2];    void init()    {        for(int i = 0; i < 2; i++)            for(int j = 0; j < 2; j++)                mt[i][j] = 0;    }    void cig()    {        for(int i = 0; i < 2; i++)            mt[i][i] = 1;    }};matrix mul(matrix a, matrix b){    matrix c;    c.init();    for(int i = 0; i < 2; i++)        for(int j = 0; j < 2; j++)            for(int k = 0; k < 2; k++)            {                c.mt[i][j] += a.mt[i][k] * b.mt[k][j];            }    return c;}matrix fpow(matrix a, LL n){    matrix r;    r.init();    r.cig();    while(n > 0)    {        if(n & 1)            r = mul(r, a);        a = mul(a, a);        n >>= 1;    }    return r;}ull fun(LL p, LL q, LL n){    if(n < 1)    {        return 2;    }    matrix base;    base.mt[0][0] = p;    base.mt[0][1] = -q;    base.mt[1][0] = 1;    base.mt[1][1] = 0;    base = fpow(base, n - 1);    ull ans = base.mt[0][0] * p + base.mt[0][1] * 2;    return ans;}int main(){    int T;    int cnt = 0;    cin >> T;    while(T--)    {        LL n, p , q;        scanf("%lld%lld%lld", &p, &q, &n);        ull ans = fun(p, q, n);        printf("Case %d: %llu\n", ++cnt, ans);    }    return 0;}//f(n) = (a+b)*f(n-1) - (ab)*f(n-2)

LightOJ 1070 - Algebraic Problem 推导+矩阵快速幂