HDU 1757

简单的矩阵构造题，参看我前几篇的谈到的矩阵的构造法。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int Mod;
struct Matrax {
	int m[15][15];
};
Matrax a,per;
int ats[15],an[15];

void initial(){
	memset(per.m,0,sizeof(per.m));
	memset(a.m,0,sizeof(a.m));
	for(int i=0;i<10;i++){
		a.m[i][0]=ats[i];
		per.m[i][i]=1;
	}
	for(int i=1;i<10;i++){
		a.m[i-1][i]=1;
	}
	for(int i=0;i<10;i++)
	an[i]=10-i-1;
}

Matrax multi(Matrax a,Matrax b){
	Matrax c;
	for(int i=0;i<10;i++){
		for(int j=0;j<10;j++){
			c.m[i][j]=0;
			for(int k=0;k<10;k++)
			c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
		}
	}
	return c;
}

Matrax Power(int k){
	Matrax ans=per,p=a;
	while(k){
		if(k&1){
			ans=multi(ans,p);
		}
		k>>=1;
		p=multi(p,p);
	}
	return ans;
}

int main(){
	int k;
	while(scanf("%d%d",&k,&Mod)!=EOF){
		for(int i=0;i<10;i++)
		scanf("%d",&ats[i]);
		if(k<10){
			printf("%d
",k);
			continue;
		}
		initial();
		Matrax ans=Power(k-9);
		int sum=0;
		for(int i=0;i<10;i++)
		sum=(sum+an[i]*ans.m[i][0])%Mod;
		printf("%d
",sum);
	}
	return 0;
}