HDU2604 Queuing

　　原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2604

　　矩阵乘法，得到递推公式，构造系数矩阵，然后进行快速幂。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int L, M;
 5 
 6 struct mat
 7 {
 8     int m[4][4];
 9     mat()
10     {memset(m, 0, sizeof m);}
11     
12     void init()
13     {
14         memset(m, 0, sizeof m);
15         m[0][0] = m[0][2] = m[0][3] = m[1][0] = m[2][1] = m[3][2] = 1;
16     }
17     
18     void unit()
19     {
20         for(int i = 0; i < 4; i ++)
21         for(int j = 0; j < 4; j ++)
22             m[i][j] = (i == j);
23     }
24 }A, B;
25 
26 
27 int F4[5] = {0, 2, 4, 6, 9};
28 
29 mat operator *(mat a, mat b)
30 {
31     mat c;
32     for(int i = 0; i < 4; i ++)
33     for(int j = 0; j < 4; j ++)
34     for(int k = 0; k < 4; k ++)
35         c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % M;
36     
37     return c;
38 }
39 
40 
41 int main()
42 {
43     while(scanf("%d%d", &L, &M) == 2)
44     {
45         if(L <= 4)
46         {
47             printf("%d\n", F4[L] % M);
48             continue;
49         }
50         A.init(); B.unit();
51         for(L -= 4; L; L >>= 1, A = A * A)
52             if(L & 1) B = B * A;
53         int ans = 0;
54         for(int i = 0; i < 4; i ++)
55             ans += B.m[0][i] * F4[4-i];
56         printf("%d\n", ans % M);
57     }
58     return 0;
59 }