hdu2604Queuing 矩阵快速幂

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
//给定队列长度
//队列的每个位置可以是f或m
//问这个队列中没有fmf和fff的情况的个数
//设f[n]为满足要求的队列为n的情况个数
//当最后一位是m时 ， 满足条件为f[n-1]
//当最后一位是f时 ， 最后两位是fm和ff两个都不满足
//当最后两位是fm和ff时 ， 最后三位是fmf , fmm , ffm , fff
//fmf和fff不满足 , fmm满足 所以有f[n-3]
//当最后三位是ffm时 ， 最后四位为ffmm , ffmf , 
//ffmm 满足 ， ffmf不满足
//所以f[n] = f[n-1] + f[n-3] + f[n-4]
//构建矩阵
// |f[n]  |    |1 1 0 1|   |f[n-1]|
// |f[n-1]| =  |0 1 0 0| * |f[n-2]|
// |f[n-2]|    |0 0 1 0|   |f[n-3]|
// |f[n-3]|    |0 0 0 1|   |f[n-4]|
//利用矩阵快速幂可以求
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 10 ;
struct node
{
    int p[maxn][maxn] ;
};
int mod ; int n = 4 ;
node mul(node a , node b)
{
    node c ;
    memset(c.p , 0 , sizeof(c.p)) ;
    for(int i = 1;i <= n;i++)
      for(int j = 1;j <= n;j++)
        for(int k = 1;k <= n;k++)
        c.p[i][j] = (c.p[i][j] + a.p[i][k]*b.p[k][j])%mod ;
    return c ;
}
node pow(node a , int k)
{
    node c ;
    memset(c.p , 0 , sizeof(c.p)) ;
    for(int i = 1;i <= n;i++)
    c.p[i][i] = 1 ;
    while(k)
    {
        if(k&1)c = mul(c, a) ;
        a = mul(a , a) ;
        k >>= 1 ;
    }
    return c ;
}
int main()
{
    int l ;
    while(~scanf("%d%d" , &l , &mod))
    {
        node a ;
        memset(a.p , 0 , sizeof(a.p)) ;
        a.p[1][1] = a.p[1][3] = a.p[1][4] = 1 ;
        a.p[2][1] = a.p[3][2] = a.p[4][3] = 1 ;
        int ans[maxn] ;
        ans[1] = 2 ; ans[2] = 4; ans[3] = 6 ;
        ans[4] = 9;
        if(l <= 4)
        {
            cout<<ans[l]%mod<<endl;
            continue  ;
        }
        node c = pow(a , l-4) ;
        cout<<(c.p[1][1]*ans[4]+c.p[1][2]*ans[3]+c.p[1][3]*ans[2]+c.p[1][4]*ans[1])%mod<<endl;
     }
     return 0 ;
}