记录编号	435212	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]简单的AVL树	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-08-09 10:58:44	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef unsigned long long LL;

inline void Pow(LL x);

LL N, p;
LL res[3][3] = {{1, 0, 0},
                 {0, 1, 0},
                 {0, 0, 1}};
LL P[3][3] = {{0, 1, 0},
               {1, 1, 0},
               {0, 1, 1}};
LL ans[1][3] = {0, 1, 1};
LL temp[3][3];

int main() { 
#ifndef LOCAL
    freopen("AVL.in", "r", stdin);
    freopen("AVL.out", "w", stdout);
#endif
    scanf("%lld%lld", &N, &p);
    //for(LL i = 2; i <= N; ++i) { 
    //    tmp = pre;
    //    pre = now;
    //    now = now % p + tmp % p + 1;
    //}
    Pow(N);
    memset(temp, 0x00, sizeof(temp));
    for(char i = 0; i < 1; ++i) 
        for(char j = 0; j < 3; ++j) 
            for(char k = 0; k < 3; ++k) 
                (temp[i][j] += ans[i][k] * res[k][j]) %= p;
    printf("%lld", temp[0][0]);
    return 0;
}

inline void Pow(LL x) { 
    while(x) { 
        if(x & 1) { 
            memset(temp, 0x00, sizeof(temp));
            for(char i = 0; i < 3; ++i) 
                for(char j = 0; j < 3; ++j) 
                    for(char k = 0; k < 3; ++k) 
                        (temp[i][j] += res[i][k] * P[k][j]) %= p;
            for(char i = 0; i < 3; ++i) 
                for(char j = 0; j < 3; ++j) 
                    res[i][j] = temp[i][j];
        }
        memset(temp, 0x00, sizeof(temp));
        for(char i = 0; i < 3; ++i) 
            for(char j = 0; j < 3; ++j) 
                for(char k = 0; k < 3; ++k) 
                    (temp[i][j] += P[i][k] * P[k][j]) %= p;
        for(char i = 0; i < 3; ++i) 
            for(char j = 0; j < 3; ++j) 
                P[i][j] = temp[i][j];
        x >>= 1;
    }
    return ;
}