HDU 1757（A Simple Math Problem）

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.

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.

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

这里就是构造一下矩阵 然后依然是矩阵的多次幂 我前面说的很详细，如果看的不清楚可以看我别的文章
构造一个矩阵
 

就求a^(t-9)*b
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct M {
	int s[11][11];
};
int n,p;
struct M multiply(struct M a,struct M b){
	struct M c;
	memset(c.s,0,sizeof(c.s));
	for(int i=1;i<=10;i++)
		for(int j=1;j<=10;j++)
			for(int k=1;k<=10;k++)
				c.s[i][j]=(c.s[i][j]+(a.s[i][k]*b.s[k][j])%p)%p;
	return c;
}
struct M paw(struct M a,int t){
	if(t==1)
		return a;
	else{
		struct M b=paw(a,t/2);
		if(t&1){
			return multiply(multiply(b,b),a);
		}
		else
			return multiply(b,b);
	}
}
int main(){
	struct M a,b,c;
	int t;
	memset(a.s,0,sizeof(a.s));
	memset(b.s,0,sizeof(b.s));
	for(int i=1;i<=10;i++)
		b.s[i][1]=10-i;
	for(int i=2;i<=10;i++)
		a.s[i][i-1]=1;
	while(scanf("%d %d",&t,&p)!=EOF){
		for(int i=1;i<=10;i++)
			scanf("%d",&a.s[1][i]);
		if(t<=9){
			printf("%d\n",t);
			continue;
		}
		c=paw(a,t-9);
		c=multiply(c,b);
		printf("%d\n",c.s[1][1]);
	}
	return 0;

}