矩陣乘法快速冪

今天員工小c寫題的時候遇到了在第四黑廠時期就沒填的坑，今日再次見面，自然是無奈，但是他請教了他的好朋友楓系，原來需要矩陣乘法快速冪的知識，

Number Sequence
時間限制: 1 Sec  記憶體限制: 256 MB
題目描述
此題HDUOJ資料過水，網上題解中直接將n%49的做法是錯誤的，
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

輸入
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

輸出
For each test case, print the value of f(n) on a single line.

樣例輸入
1 1 3
1 2 10
0 0 0

樣例輸出
2
5

這就是小c遇到的題目，小c最早找規律半天也沒找出來，就去問度娘，結果度娘所有答案都是%49，小C一看，穩了，馬上又A一題，（第n次不讀題，題上說了%49錯的） Ctrl C+Ctrl V = WA，非常尷尬，

然后小c沒辦法呀，只能請教他的新朋友楓系，楓系二話不說，就很仗義地把自己的代碼展示給了小C，小C一看兩看三看四看都看不明白，后來才知道這是矩陣乘法快速冪，可惜網上的博客并沒有教會小C，于是小C只能再次求助楓系，

原來矩陣乘法快速冪需要線性代數的知識，還好小C也是個帶學生，這題看似是斐波那契遞推的升級版，實則應該采用矩陣的方法優化，

圖片來自楓系，說實話這個圖清晰明了，網上博客要是有個這圖，小C早會了（逃

這是代碼，也可以當作模板采用，注釋的非常詳細，

#include<bits/stdc++.h>//本代碼來自于一位小c的好朋友楓系，向他表示感謝，他教會了我，我才能教給大家 
using namespace std;
struct juzhen
{
	int x[2][2];//定義一個矩陣 
};
juzhen mul(juzhen a,juzhen b)//這個部分是用作矩陣相乘的模擬; 
{
	juzhen c;//定義一個矩陣型別的c 
	memset(c.x,0,sizeof(c.x));//將c初始化 
	for(int i=0;i<2;i++)//矩陣乘法大模擬 
		for(int j=0;j<2;j++)//這個需要學過線性代數才能模擬 
			for(int k=0;k<2;k++)//線性代數應該是大一的東西 
				c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%7;//當然也不是很難，百度看一看就會了 
	return c;
}
juzhen pow(juzhen now,int n)//矩陣版本的快速冪 
{
	juzhen ans;//定義一個juzhen型別的ans，矩陣初始化*4，main函式那里說了 
	ans.x[0][0]=1;//左上角a       矩陣 
	ans.x[0][1]=0;//右上角b      a   b 
	ans.x[1][0]=0;//左下角1      1   0
	ans.x[1][1]=1;//右下角0 
	while(n)
	{
		if(n&1)//如果這一位是1 
			ans=mul(ans,now);//ans就乘以一下 
		now=mul(now,now);//now進位 
		n=n/2;//n右移一位 
	}
	return ans;//回傳ans 
}
void print(juzhen a)//此處是用來在寫矩陣的時候檢查用的，交代碼的時候不呼叫，不是我的代碼，就把它留作紀念吧 
{
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
			cout<<a.x[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int a,b,c;
	for(cin>>a>>b>>c;!(a==0&&b==0&&c==0);cin>>a>>b>>c)
	{
		if(c==1||c==2)//一和二就直接輸出吧 
			cout<<1;
		else  
		{
			juzhen ans;//定義一個juzhen型別的ans 
			ans.x[0][0]=a;//左上角a       矩陣 
			ans.x[0][1]=b;//右上角b      a   b 
			ans.x[1][0]=1;//左下角1      1   0
			ans.x[1][1]=0;//右下角0 
			ans=pow(ans,c-1);//跟快速冪一樣 
			cout<<(ans.x[1][0]+ans.x[1][1])%7;//輸出題目要求的%7 f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
		}
		cout<<endl; 
	}
	return 0;
}

?
#include<bits/stdc++.h>//本代碼來自于一位小c的好朋友楓系，向他表示感謝，他教會了我，我才能教給大家 
using namespace std;
struct juzhen
{
	int x[2][2];//定義一個矩陣 
};
juzhen mul(juzhen a,juzhen b)//這個部分是用作矩陣相乘的模擬; 
{
	juzhen c;//定義一個矩陣型別的c 
	memset(c.x,0,sizeof(c.x));//將c初始化 
	for(int i=0;i<2;i++)//矩陣乘法大模擬 
		for(int j=0;j<2;j++)//這個需要學過線性代數才能模擬 
			for(int k=0;k<2;k++)//線性代數應該是大一的東西 
				c.x[i][j]=(c.x[i][j]+a.x[i][k]*b.x[k][j])%7;//當然也不是很難，百度看一看就會了 
	return c;
}
juzhen pow(juzhen now,int n)//矩陣版本的快速冪 
{
	juzhen ans;//定義一個juzhen型別的ans，矩陣初始化*4，main函式那里說了 
	ans.x[0][0]=1;//左上角a       矩陣 
	ans.x[0][1]=0;//右上角b      a   b 
	ans.x[1][0]=0;//左下角1      1   0
	ans.x[1][1]=1;//右下角0 
	while(n)
	{
		if(n&1)//如果這一位是1 
			ans=mul(ans,now);//ans就乘以一下 
		now=mul(now,now);//now進位 
		n=n/2;//n右移一位 
	}
	return ans;//回傳ans 
}
void print(juzhen a)//此處是用來在寫矩陣的時候檢查用的，交代碼的時候不呼叫，不是我的代碼，就把它留作紀念吧 
{
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
			cout<<a.x[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int a,b,c;
	for(cin>>a>>b>>c;!(a==0&&b==0&&c==0);cin>>a>>b>>c)
	{
		if(c==1||c==2)//一和二就直接輸出吧 
			cout<<1;
		else  
		{
			juzhen ans;//定義一個juzhen型別的ans 
			ans.x[0][0]=a;//左上角a       矩陣 
			ans.x[0][1]=b;//右上角b      a   b 
			ans.x[1][0]=1;//左下角1      1   0
			ans.x[1][1]=0;//右下角0 
			ans=pow(ans,c-1);//跟快速冪一樣 
			cout<<(ans.x[1][0]+ans.x[1][1])%7;//解釋看下方圖片 
		}
		cout<<endl; 
	}
	return 0;
}

?