记录编号	584961	评测结果	AAAAAAAAAA
题目名称	偷笔记	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.531 s
提交时间	2023-11-17 15:30:14	内存使用	2.78 MiB

#include <bits/stdc++.h>
using namespace std;
const int mod = 666;
int n,m;
struct Matrix{
    int a[151][151],n,m;
    void clear(){n = m = 0;memset(a,0,sizeof(a));}
    Matrix operator * (const Matrix &x){
        Matrix y;y.clear();
        y.n = n;y.m = m;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                for(int k = 1;k <= m;k++)
                    y.a[i][j] = (y.a[i][j] + (a[i][k] * x.a[k][j]) % mod) % mod;
        return y;
    }
}c,f;
int main(){
    freopen("burglar.in","r",stdin);
    freopen("burglar.out","w",stdout);
    scanf("%d%d",&n,&m);
    f.n = 1,f.m = 3*n;
    f.a[1][1] = 1,f.a[1][2] = 1,f.a[1][n+1] = 1;//原始矩阵 
    if(m == 1){printf("%d\n",f.a[1][2*n]);return 0;}
    if(m == 2){printf("%d\n",f.a[1][n]);return 0;}
    m -= 2;
    c.n = 3*n,c.m = 3*n;
    for(int i = 1;i <= n;i++){
        if(i > 1)c.a[i-1][i] = 1,c.a[2*n+i-1][i] = 1;
        c.a[i][i] = 1,c.a[2*n+i][i] = 1;
        if(i < n)c.a[i+1][i] = 1,c.a[2*n+i+1][i] = 1;
    } 
    for(int i = n+1;i <= 2*n;i++)c.a[i-n][i] = 1,c.a[i+n][i] = 1;
    for(int i = 2*n+1;i <= 3*n;i++)c.a[i-n][i] = 1;
        //建转移矩阵 
    while(m){
        if(m & 1)f = f * c;
        c = c * c;
        m >>= 1;
    }
    printf("%d\n",f.a[1][n]);
    
    return 0;
    
}