UVA10655 Contemplation! Algebra —— 推公式、矩阵快速幂

题目链接：https://vjudge.net/problem/UVA-10655

题意：

a+b、ab的值分别为p、q，求a^n+b^n。

题解：

1.a、b未知，且直接求出a、b也不太实际。

2.看到 a^n+b^n 这个式子就想到二阶齐次递推式的通项公式，然后就想是否能通过通项公式反推回递推式。结果发现a、b的值是不能确定是否相等的，而求二阶齐次递推式的通项公式时，是需要根据根的情况来分类求解的，所以此题不适应。

3.那么，就直接对 a^n+b^n 做一下变形：

4.得到递推式之后，就直接构造矩阵，然后快速幂。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+7;
const int MAXN = 1e6+100;

const int Size = 2;
struct MA
{
    LL mat[Size][Size];
    void init()
    {
        for(int i = 0; i<Size; i++)
        for(int j = 0; j<Size; j++)
            mat[i][j] = (i==j);
    }
};

MA mul(MA x, MA y)
{
    MA ret;
    memset(ret.mat, 0, sizeof(ret.mat));
    for(int i = 0; i<Size; i++)
    for(int j = 0; j<Size; j++)
    for(int k = 0; k<Size; k++)
        ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j];
    return ret;
}

MA qpow(MA x, LL y)
{
    MA s;
    s.init();
    while(y)
    {
        if(y&1) s = mul(s, x);
        x = mul(x, x);
        y >>= 1;
    }
    return s;
}


int main()
{
    LL p, q, n, f[2];
    while(scanf("%lld%lld%lld", &p,&q,&n)==3)
    {
        f[0] = 2; f[1] = p;
        if(n<=1)
        {
            printf("%lld
", f[n]);
            continue;
        }

        MA s;
        memset(s.mat, 0, sizeof(s.mat));
        s.mat[0][0] = p; s.mat[0][1] = -q;
        s.mat[1][0] = 1; s.mat[1][1] = 0;

        s = qpow(s, n-1);
        LL ans = 1LL*s.mat[0][0]*f[1] + 1LL*s.mat[0][1]*f[0];
        printf("%lld
", ans);
    }
}