【HDU1005】Number Sequence(矩阵乘法)

Categories: 数据结构和算法
Tags: ,
Comments: 2 Comments
Published on: 2011 年 09 月 16 日

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).
题意:给出一个递推公式,求第N项。
题解:开始试图找出一个能够直接算的递推公式,没找到,所以考虑矩阵乘法。根据给出的递推公式可以设想:

然后使用矩阵乘法时间复杂度为log(n)的一个算法,(模板代码),具体算法讲解可由指数算法推广得出。即 x^n=(x^2)^(n/2)。细节请看模板代码。

    
#include<cstring>
#include<iostream>
using namespace std;
#define N 2
#define MOD 7
struct Matrix
{
	int m[2][2];
};
void  matrixMultiplication(Matrix &res,int n)
{
	Matrix tm,tm1;
	int i,j,k;
	tm=res;
	for (i=0;i<N;i++)
		for (int j=0;j<N;j++)
		{
			res.m[i][j]=(i==j);
		}
		if(n==0){ return; }
		while(n)
		{

			if(n&1)
			{
				memset(tm1.m,0,sizeof(tm1.m));
				for (i=0;i<N;i++)
				{
					for (j=0;j<N;j++)
					{
						for(k=0;k<N;k++)
						{
							tm1.m[i][j] += (res.m[i][k]*tm.m[k][j])%MOD;
							tm1.m[i][j] %= MOD;
						}
					}
				}
				res=tm1;
			}
			memset(tm1.m,0,sizeof(tm1.m));
			for (i=0;i<N;i++)
			{
				for (j=0;j<N;j++)
				{
					for(k=0;k<N;k++)
					{
						tm1.m[i][j] += (tm.m[i][k]*tm.m[k][j])%MOD;
						tm1.m[i][j] %= MOD;
					}
				}
			}
			tm=tm1;
			n>>=1;
		}
}
int main(){
	freopen("1.txt","r",stdin);
	Matrix mat;
	int n;
	while(cin>>mat.m[0][0]>>mat.m[0][1]>>n){
		if(mat.m[0][0]==0 && mat.m[0][1]==0 &&n ==0)
			break;
		if(n<3) {cout<<"1"<<endl; continue; }
		mat.m[1][0]=1;mat.m[1][1]=0;
		matrixMultiplication(mat,n-2);
		cout<<(mat.m[0][0]+mat.m[0][1])%MOD<<endl;
	}
}

我猜你可能也喜欢:

2 Comments - Leave a comment
  1. […] 参考:http://blog.pureisle.net/archives/887.html […]

  2. […] 当然,这题还有另外的解法,详见 【HDU1005】Number Sequence(矩阵乘法) […]

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日