学步园

hdu1757A Simple Math Problem

问题是怎么转化成矩阵相乘的呢？请参考：http://blog.csdn.net/fangzhiyang/article/details/6929747

看懂了思路再用自己的代码实现

（二维数组真心不方便，下次换结构体）

#include<iostream>
using namespace std;

int m0[11][11],m1010[11][11],m[2][11];
int k,N;

void Cal(int n)
{
	int i,j,k,t[11][11];
	memset(t,0,sizeof(t));
	if(n==1)
	{
		for(i=1;i<=10;i++)
			for(j=1;j<=10;j++)
				for(k=1;k<=10;k++)
					t[i][j]+=((m0[i][k]%N)*(m0[k][j])%N)%N;
		
		for(i=1;i<=10;i++)
			for(j=1;j<=10;j++)
				m0[i][j]=t[i][j];
	}
	else
	{
		for(i=1;i<=10;i++)
			for(j=1;j<=10;j++)
				for(k=1;k<=10;k++)
					t[i][j]+=((m1010[i][k]%N)*(m0[k][j])%N)%N;
		
		for(i=1;i<=10;i++)
			for(j=1;j<=10;j++)
				m1010[i][j]=t[i][j];
	}
}

void Cal1010(int n)    //快速幂乘计算m0的n次方储存于m1010 
{
	memset(m1010,0,sizeof(m1010));
	for(int i=1;i<=10;i++)
		m1010[i][i]=1;
	while(n)
	{
		if(n&1)	Cal(2);
		n>>=1;
		Cal(1);
	}
}

void Cal110()           //m与m1010相乘 
{
	int i,j,k,t[2][11];
	memset(t,0,sizeof(t));
	for(j=1;j<=10;j++)
		for(k=1;k<=10;k++)
			t[1][j]+=m[1][k]*m1010[k][j];
	for(i=1;i<=10;i++)
		m[1][i]=t[1][i];
} 

main()
{
	int i,j;
	while(scanf("%d%d",&k,&N)!=EOF)
	{
		
		//-----------------------------------------------------------------
		memset(m0,0,sizeof(m0));		           //
		for(i=2;i<=10;i++) m0[i][i-1]=1;           //
		for(i=10;i>=1;i--)				           //给最基础的矩阵m0赋值
			scanf("%d",&m0[i][10]);                //
		//------------------------------------------------------------------
		
		if(k>9)
		{
			for(i=i;i<=10;i++) m[1][i]=i-1;
			Cal1010(k-9);
			Cal110();
			printf("%d\n",m[1][10]%N);
		}
		else
		printf("%d\n",k%N);
	}
}