【矩阵快速幂-构造】I – Algebraic Problem LightOJ – 1070

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 00.

Output
For each test case, print the case number and (an+bn) modulo 264.

Sample Input
2

10 16 2

7 12 3

Sample Output
Case 1: 68

Case 2: 91

$a^n+b^n 很容易想到和a^(n-1)+b^(n-1)$相关。再乘上初始的$a+b$。有一个量总是不变化的，所以想到矩阵。演算几下可以发现$(f(n-1) f(n-2)) \begin{matrix} a+b & 1 \\ -ab & 0 \\ \end{matrix} \tag{1} = (f(n) f(n-1))$

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
struct Mat{
ll a[5][5];
Mat(){
memset(a,0,sizeof(a));
}
};
Mat mul(Mat a,Mat b)
{
Mat res=Mat();
for(ll i=1;i<=2;i++)
{
for(ll j=1;j<=2;j++)
{
for(ll k=1;k<=2;k++)
{
res.a[i][j]+=a.a[i][k]*b.a[k][j];
}
}
}
return res;
}
Mat ksm(Mat n,ll k)
{
Mat ans=Mat();
for(ll i=1;i<=2;i++)
ans.a[i][i]=1;
while(k)
{
if(k&1) ans=mul(n,ans);
n=mul(n,n);
k>>=1;
}
return ans;
}
Mat mul2(Mat a,Mat b)
{
Mat res=Mat();
for(ll i=1;i<=1;i++)
{
for(ll j=1;j<=2;j++)
{
for(ll k=1;k<=2;k++)
{
res.a[i][j]+=a.a[i][k]*b.a[k][j];
}
}
}
return res;
}
int main()
{
ll t,q,p,n;
scanf("%llu",&t);
for(ll i=1;i<=t;i++)
{
scanf("%lld%lld%lld",&p,&q,&n);
Mat p1=Mat();
p1.a[1][1]=p;p1.a[1][2]=1;
p1.a[2][1]=-q;p1.a[2][2]=0;
Mat f=Mat();
f.a[1][1]=p;f.a[1][2]=2;
printf("Case %llu: ",i);
if(n==0)
{
printf("2\n");
continue;
}
Mat p2=ksm(p1,n-1);
Mat a1=mul2(f,p2);
printf("%llu\n",a1.a[1][1]);
}

}