Uva 10655 已知a+b,ab 求a^n+b^n 矩阵快速幂

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1596&mosmsg=Submission+received+with+ID+13202019

#include<stdio.h>
#include<queue>
#include<string.h>
#include<iostream>
using namespace std;
#define Matr 2 //矩阵大小,注意能小就小
#define ll long long
struct mat//矩阵结构体，a表示内容，size大小 矩阵从1开始
{
    ll a[Matr][Matr],size;
    mat()
    {
        size=0;
        memset(a,0,sizeof(a));
    }
};

mat multi(mat m1,mat m2)//两个相等矩阵的乘法，对于稀疏矩阵，有0处不用运算的优化 
{
    mat ans=mat();    ans.size=m1.size;
    for(int i=0;i<m1.size;i++)
        for(int j=0;j<m2.size;j++)
            if(m1.a[i][j])//稀疏矩阵优化 
                for(int k=0;k<m1.size;k++)
                    ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k]);

    return ans;
}
mat quickmulti(mat m,ll n)//二分快速幂 
{
    mat ans=mat();
    int i;
    for(i=0;i<m.size;i++)ans.a[i][i]=1;
    ans.size=m.size;
    while(n)
    {
        if(n&1)ans=multi(m,ans);
        m=multi(m,m);
        n>>=1;
    }
    return ans;
}

ll p, q, n;
int main(){
	while(cin>>p>>q>>n){
		
		if(n==0){cout<<2<<endl;continue;}
		if(n==1){cout<<p<<endl;continue;}
		if(n==2){cout<<p*p-2*q<<endl;continue;}
		mat a=mat();
		a.size = 2;
		a.a[0][0] = p; a.a[0][1] = -q;
		a.a[1][0] = 1; a.a[1][1] = 0;
		a = quickmulti(a,n-1);
		ll x2 = p*p-2*q;
		ll ans = a.a[0][0]*p + 2*a.a[0][1];
		cout<<ans<<endl;
	}
	return 0;
}

Uva 10655 已知a+b,ab 求a^n+b^n 矩阵快速幂

原文：http://blog.csdn.net/acmmmm/article/details/19824395