题干：

Lele now is thinking about a simple function f(x). 

If x < 10 f(x) = x. 
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10); 
And ai(0<=i<=9) can only be 0 or 1 . 

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m. 

Input

The problem contains mutiple test cases.Please process to the end of file. 
In each case, there will be two lines. 
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9. 

Output

For each case, output f(k) % m in one line.

Sample Input

10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0

Sample Output

45
104

 

题目大意：

  告诉你f(x)的运算式，输入k和m，输出f(k)%m

解题报告：

  好久不写博客了。。来复习一波矩阵快速幂吧、、

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll mod,k;
ll a[15];
struct Matrix {
	ll arr[15][15];//其实应该是11*11的 
} unit;
Matrix Mul(Matrix a,Matrix b) {
	Matrix c;
	for(int i = 1; i<=11; i++) {
		for(int j = 1; j<=11; j++) {
			c.arr[i][j]=0;
			for(int k = 1; k<=11; k++) {
				c.arr[i][j] = (c.arr[i][j] + a.arr[i][k]*b.arr[k][j])%mod;
			}
		}
	}
	return c;
}
Matrix qpow(Matrix a,ll k) {
	Matrix res = unit;
	while(k) {
		if(k&1) res = Mul(res,a);
		a=Mul(a,a);
		k>>=1;
	}
	
	return res;
}
int main()
{
	for(int i = 1; i<=11; i++) {
		unit.arr[i][i]=1;
	}
	while(~scanf("%lld%lld",&k,&mod)) {
		for(int i = 1; i<=10; i++) scanf("%lld",a+i);
		Matrix trans;
		//INIT 
		for(int i = 1; i<=11; i++) {
			for(int j = 1; j<=11; j++) {
				if(i == 1) trans.arr[i][j] = a[j];
				else {
					if(i-1 == j) trans.arr[i][j] = 1;
					else trans.arr[i][j]=0;
				}
			}
		}
		
		if(k <= 9) {
			printf("%lld\n",k);
		}
		else {
			Matrix ans = qpow(trans,k-9);
			ll out = 0;
			for(int i = 1; i<=10; i++) {
				out += ans.arr[1][i]*(10-i);
				out %= mod;
			}
			printf("%lld\n",out);
		}
		
	}
	return 0 ;
 }