求递推式，构造一个矩阵，根据矩阵乘法规则，得到f(n)=a1f(n-1)+a2f(n-2)+…+am*f(n-m)的第N项。

A Simple Math ProblemHDU1757

Problem Description

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

题意：

第0项到第9项都是自己，后面的都是满足递推式的f(n)，求第n项模m.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <stdio.h>
#include<string.h>
using namespace std;
int k, m;
struct matrix
{
	int  g[15][15];
	int n;
	matrix operator=(const matrix &b)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				g[i][j] = b.g[i][j];
			}
		}
		return *this;
	}
};
matrix operator*(const matrix &a, const matrix &b)
{
	matrix c;
	int sum;
	for (int i = 0; i < a.n; i++)
	{
		for (int j = 0; j < a.n; j++)
		{
			int I;
			sum = 0;
			for (I = 0; I < a.n; I++)
			{
				sum = sum%m + (a.g[i][I] * b.g[I][j] % m);
				sum %= m;
			}
			c.g[i][j] = sum;
		}
	}
	return c;
}
matrix pow(matrix a, int b)
{
	matrix ans, base = a;
	ans.n = 10;
	for (int i = 0; i < ans.n; i++)
	{
		for (int j = 0; j < ans.n; j++)
		{
			if (i == j)
				ans.g[i][j] = 1;
			else ans.g[i][j] = 0;
		}
	}
	while (b)
	{
		if (b & 1)
		{
			ans = ans * base;
		}
		base = base * base;
		b >>= 1;
	}
	return ans;
}
int main()
{
	while (~scanf("%d%d", &k, &m))
	{
		matrix a, b;
		a.n = 10;
		b.n = 10;
		memset(a.g, 0, sizeof(a.g));
		memset(b.g, 0, sizeof(b.g));
		for (int i = 0; i < 10; i++)
		{
			scanf("%d", &b.g[i][0]);
			b.g[i][i + 1] = 1;
			a.g[0][i] = 9 - i;
		}
		if (k < 10)
		{
			cout << k << endl; continue;
		}
		k -= 9;
		b = pow(b, k);
		a = a*b;
		cout << a.g[0][0] << endl;
	}
}