HDU 1757 A Simple Math Problem（ 矩阵快速幂 ）

---

<font color = red , size = '4'>下列图表转载自 efreet

链接：传送门

题意：给出递推关系，求 f(k) % m 的值，

思路：

• 因为 k<2 * 10^9 , m < 10^5，O(n)算法应该是T掉了，当 k >= 10 时 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)，可以理解为这是两个行列是乘积的值，经下面分析可知用矩阵快速幂可搞

• 下列三个表分别命名为矩阵0，矩阵1，矩阵2。

fk	0	0	0	0	0	0	0	0	0
fk-1	0	0	0	0	0	0	0	0	0
fk-2	0	0	0	0	0	0	0	0	0
fk-3	0	0	0	0	0	0	0	0	0
fk-4	0	0	0	0	0	0	0	0	0
fk-5	0	0	0	0	0	0	0	0	0
fk-6	0	0	0	0	0	0	0	0	0
fk-7	0	0	0	0	0	0	0	0	0
fk-8	0	0	0	0	0	0	0	0	0
fk-9	0	0	0	0	0	0	0	0	0

等于

a0	a1	a2	a3	a4	a5	a6	a7	a8	a9
1	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	1	0	0	0	0
0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	0	1	0

乘以

fk-1	0	0	0	0	0	0	0	0	0
fk-2	0	0	0	0	0	0	0	0	0
fk-3	0	0	0	0	0	0	0	0	0
fk-4	0	0	0	0	0	0	0	0	0
fk-5	0	0	0	0	0	0	0	0	0
fk-6	0	0	0	0	0	0	0	0	0
fk-7	0	0	0	0	0	0	0	0	0
fk-8	0	0	0	0	0	0	0	0	0
fk-9	0	0	0	0	0	0	0	0	0
fk-10	0	0	0	0	0	0	0	0	0

- 经过观察发现，当 k >= 10 时 f(k) = [ 矩阵1 ]^(k-9) * [ 矩阵2 ]

---

/*************************************************************************

    > File Name: hdu1757.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月02日 星期二 19时25分30秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 11;

int MOD;

#define ll long long

#define mod(x) ((x)%MOD)

struct mat{

	int m[maxn][maxn];

}unit;

int n;

mat operator * (mat a,mat b){

	mat ret;

	ll x;

	for(int i=0;i<10;i++){

		for(int j=0;j<10;j++){

			x = 0;

			for(int k=0;k<10;k++)

				x += mod( (ll)a.m[i][k]*b.m[k][j] );

			ret.m[i][j] = mod(x);

		}

	}

	return ret;

}

// 初始化单位阵

void init_unit(){

	for(int i=0;i<10;i++)

		unit.m[i][i] = 1;

	return;

}

mat pow_mat(mat a,ll x){

	mat ret = unit;

	while(x){

		if(x&1)	ret = ret*a;

		a = a*a;

		x >>= 1;

	}

	return ret;

}

int main(){

	mat a , f;

	int aa[10];

	ll  k;

	init_unit();

	memset(f.m,0,sizeof(f.m));

	for(int i=0;i<10;i++)	f.m[i][0] = 9-i;

	while(cin>>k>>MOD){

		for(int i=0;i<10;i++)	cin>>aa[i];

		if(k<10)	printf("%lld\n",k);

		else{

			// 构建a矩阵

			for(int j=0;j<10;j++)	a.m[0][j] = aa[j];

			for(int i=1;i<10;i++){

				for(int j=0;j<10;j++){

					if(j+1==i)	a.m[i][j] = 1;

					else		a.m[i][j] = 0;

				}

			}

			mat ans = pow_mat(a,k-9);

			ans = ans*f;

			printf("%d\n",ans.m[0][0]%MOD);

		}

	}

	return 0;

}