【HDOJ】2604 Queuing

递推，推得f(n) = f(n-1) + f(n-3) + f(n-4)。然后转换成矩阵相乘，如下
f(n-1)  f(n-2)  f(n-3)  f(n-4)   *    1   1   0   0   =  f(n)   f(n-1)  f(n-2)  f(n-3)
0         0        0         0               0   0   1   0       0         0        0         0
0         0        0         0               1   0   0   1       0         0        0         0
0         0        0         0               1   0   0   0       0         0        0         0
从而转化为快速矩阵相乘。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #define MATN 4

 typedef struct mat_st {

     int m[MATN][MATN];

     mat_st() {

         memset(m, , sizeof(m));

     }

 } mat_st;

 int ans[MATN]={,,,};

 int mod;

 mat_st mult_mat(mat_st a, mat_st b) {

     mat_st ret;

     int i, j, k;

     for (i=; i<MATN; ++i) {

         for (j=; j<MATN; ++j) {

             for (k=; k<MATN; ++k)

                 ret.m[i][j] += a.m[i][k]*b.m[k][j];

             ret.m[i][j] %= mod;

         }

     }

     return ret;

 }

 mat_st pow_mat(mat_st a, int n) {

     mat_st ret;

     int i;

     for (i=; i<MATN; ++i)

         ret.m[i][i] = ;

     while (n) {

         if (n & )

             ret = mult_mat(ret, a);

         a = mult_mat(a, a);

         n >>= ;

     }

     return ret;

 }

 int main() {

     int l;

     int i;

     mat_st e, a;

     e.m[][] = e.m[][] = e.m[][] = e.m[][] = e.m[][] = e.m[][] = ;

     for (i=; i<MATN; ++i)

         a.m[][i] = ans[MATN--i];

     while (scanf("%d %d", &l, &mod) != EOF) {

         if (l <= )

             printf("%d\n", ans[l]%mod);

         else {

             mat_st c = pow_mat(e, l-);

             mat_st r = mult_mat(a, c);

             printf("%d\n", r.m[][]);

 #ifndef ONLINE_JUDGE

             fflush(stdout);

 #endif

         }

     }

     return ;

 }