Light OJ 1070 / Mat Expo

/***
 created: 2022-04-12-21.13.43
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'
#define row vector<ull>
#define matrix vector<vector<ull>>

matrix operator*(const matrix& a, const matrix& b)
{
    ll r,c,p;

    r=a.size();
    p=a[0].size();
    assert(p==b.size());

    /// first matrix must have the same number of columns
    ///as the second matrix has rows

    c=b[0].size();

    matrix ans(r,row(c,0));

    ll i,j,k;

    for(i=0; i<r; i++)
    {
        for(j=0; j<c; j++)
        {
            for(k=0; k<p; k++)
            {
                ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]);
            }
        }
    }
    return ans;
}

matrix bigmod(matrix &a,ll p)
{
    if(p==1) return a;

    matrix x=bigmod(a,p/2);

    x=x*x;

    if(p&1) x=(x*a);

    return x;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll a,b,c,n,m,p,q;

        cin>>p>>q>>n;

        //p=a+b, q=ab;

        matrix base = {{p,-q},{1,0}};

        matrix statem = {{p},{2}};

        cout<<"Case "<<cs<<": ";

        if(n==0) cout<<2<<nl;
        else if(n==1) cout<<p<<nl;
        else
        {
            matrix ans=bigmod(base,n-1);

            ans=ans*statem;

            cout<<ans[0][0]<<nl;
        }
    }

    get_lost_idiot;
}


/*

Solution Idea:
p = a + b, q = ab

(a ^ n + b ^)


a ^ 2 + b ^ 2 = (a + b) * (a + b) -2 * a * b

a ^ 3 + b ^ 3 = (a ^ 2 + b ^ 2) * (a + b) -a * b (a + b)

a ^ 4 + b ^ 4 = (a ^ 3 + b ^ 3) * (a + b) -a * b (a ^ 2 + b ^ 2)

1.a^n + b^n = (a^(n-1)+b^(n-1))*(a+b) - a*b*(a^(n-2)+b^(n-2))

2.  Xn = a^n + b^n

3 . Xn = pXn-1 + qXn-2

    (p q)      (Xn-1)         (pXn-1 + qXn-2)         (Xn  )
4.         x               =                      =
    (1 0)      (Xn-2)         ( Xn-1 +  0  )          (Xn-1)

5 . from this

    (p q)^(n-1)     (X1)     (Xn   )
                x          =
    (1 0)           (X0)     (Xn-1)

*/