HDU 1757 A Simple Math Problem

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

矩阵快速幂，但是我没有自己推出来，感觉都好神（是你太弱了吧。。）。别忘了取模，各种地方都要取！

CODE:

#include 
#include 
#include 
#define REP(i, s, n) for(int i = s; i <= n; i ++)
#define REP_(i, s, n) for(int i = n; i >= s; i --)
#define MAX_N 10 + 5using namespace std;int k, m;
struct node{int Mtx[MAX_N][MAX_N];
}med;void Pre_Set(){REP(i, 1, 10) scanf("%d", &med.Mtx[1][i]);REP(i, 2, 10) REP(j, 1, 10){if(i - j == 1) med.Mtx[i][j] = 1;else med.Mtx[i][j] = 0;} 
}node operator*(node a,node b){node c;REP(i, 1, 10) REP(j, 1, 10){c.Mtx[i][j] = 0;REP(k, 1, 10) c.Mtx[i][j] += a.Mtx[i][k] * b.Mtx[k][j]; c.Mtx[i][j] %= m;}return c;
}node operator^(node a,int k){if(k == 0){memset(a.Mtx, 0, sizeof(a.Mtx));REP(i, 1, 10) a.Mtx[i][i] = 1;return a;}if(k == 1) return a;node c = a ^ (k >> 1);if(k & 1) return c * c *a;return c * c;
}int main(){while(scanf("%d%d", &k, &m) != EOF){Pre_Set();if(k < 10) { cout << k % m << endl; }else {med = med ^ (k - 9);int ans = 0;REP(i, 1, 10){ans = (ans + med.Mtx[1][i] * (10 - i)) % m;}printf("%d
", ans);}}return 0;
}