a simple math problem(矩阵二分).cpp

杭电acm解题报告2001---2099.

//类似Log N 的Fibonacci数矩阵计算方法,普通Fibonacci计算方法时间复杂度是 N
//fx = fx-1 + fx-2 (x > 2)
//f1 = 1, f2 = 1
//a1 = 1, a2 = 1
//		   |0, a2|
//|f1, f2| |1, a1| = |f2, f1+f2| . f3 = f1 + f2
//
//		   |0, 1|
//|f2, f3| |1, 1| = |f3, f2+f3| . f4 也可以得出了，依次类推
//
#include <cstdio>
#include <string>

int matrix[3][11][11];
int (* pm[4])[11], (* pt)[11];
int a[11];
int k,m;

void e_matrix(int m1[][11],int n)
{
	for (int i=0;i<n;i++) {
		m1[i][i] = 1;
	}
}

inline void cal(const int m1[11][11],const int m2[11][11],int m3[11][11])
{
	for (int i=0;i<10;i++) {
		for (int j=0;j<10;j++) {
			m3[i][j] = 0;
			for (int k=0;k<10;k++) {
				m3[i][j] += (m1[i][k] * m2[k][j]) % m;
				m3[i][j] %= m;
			}
		}
	}
}

void print(int m[11][11])
{
	for (int i=0;i<10;i++) {
		for (int j=0;j<10;j++) {
			printf("%d  ",m[i][j]);
		}
		printf("\n");
	}
	printf("//////////////////////////////////////\n");
}

int main()
{
	while (scanf("%d %d",&k,&m)==2) {
		for (int i=0;i<10;i++) {
			scanf("%d",a+i);
		}
		if (k < 10) {
			printf("%d",k % m);
			continue;
		}
		for (i=0;i<3;i++) {
			pm[i] = matrix[i];
		}
		memset(matrix,0,sizeof(matrix));
		e_matrix(pm[2], 10);
		e_matrix(pm[0]+1, 9);
		for (i=0;i<10;i++) {
			pm[0][i][9] = a[9-i];
		}
		//print(pm[0]);
		
		k -= 9;
		i = 1;
		//int t1=1,t2=0;
		while (k > 1) {
			if (k%2 == 1) {
				//t2 += t1;
				cal(pm[0], pm[2], pm[1]);
				pt = pm[1];
				pm[1] = pm[2];
				pm[2] = pt;
			}
			//t1 *= 2;
			cal(pm[0], pm[0], pm[1]);
			pt = pm[1];
			pm[1] = pm[0];
			pm[0] = pt;
			//print(pm[0]);
			k = k >> 1;
		}
		//print(pm[2]);
		cal(pm[0], pm[2], pm[1]);
		pt = pm[1];
		pm[1] = pm[0];
		pm[0] = pt;
		//print(pm[0]);

		for (int j=0;j<10;j++) {
			pm[1][0][j] = 0;
			for (k=0;k<10;k++) {
				pm[1][0][j] += (k * pm[0][k][j]) % m;
				pm[1][0][j] %= m;
			}
		}
		printf("%d\n",pm[1][0][9]);
	}
}