可以理解为2663的加强版，多了些状态，代码基本参考了别人的，各种位运算。。。。因为N比较大，所以，矩阵乘法的优势就体现出来了，不过这个代码感觉速度还不是很快啊

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
//
//  main.cpp
//  p3420
//
//  Created by Silly on 13-12-26.
//  Copyright (c) 2013年 Silly. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

struct mt {
    ll ma[16][16];
};

mt res, tmp;

int N, M;
int bit[4];

void init() {
    memset(res.ma, 0, sizeof(res.ma));
    memset(tmp.ma, 0, sizeof(tmp.ma));
    for (int i = 0; i < 16; i++) {
        res.ma[i][i] = 1;
    }
    for (int i = 0; i < 4; i++) {
        bit[i] = (1 << i);
    }
}

void set_mat() {
    for (int i = 0; i < 16; i++) {
        tmp.ma[i][(~i)&0xF]++;
        for (int j = 0; j < 3; j++) {
            if ( ((~i)&bit[j]&0xF) == 0 && ((~i)&bit[j+1]&0xF) == 0) {
                tmp.ma[i][((~i)|bit[j]|bit[j+1]) & 0xF]++;
            }
        }
    }
    tmp.ma[15][15]++;
}

mt mm(mt a, mt b) {
    mt c;
    memset(c.ma, 0, sizeof(c.ma));
    for (int i = 0; i < 16; i++) {
        for (int k = 0; k < 16; k++) {
            if (a.ma[i][k]) {
                for (int j = 0; j < 16; j++) {
                    c.ma[i][j] += a.ma[i][k] * b.ma[k][j];
                }
            }
        }
    }
    for (int i = 0; i < 16; i++) {
        for (int j = 0 ; j < 16; j++) {
            c.ma[i][j] %= M;
        }
    }
    return c;
}

void mat_pw() {
    for (int i = 0; i < 31; i++) {
        if (N & (1 << i))
            res = mm(res, tmp);
        tmp = mm(tmp, tmp);
    }
}

int main(int argc, const char * argv[])
{
    while (scanf("%d%d", &N, &M) && N|M) {
        init();
        set_mat();
        mat_pw();
        printf("%lldn", res.ma[15][15]);
    }
    return 0;
}