上周的3*N的骨牌,因为状态只有8中,所以我们可以手算出状态转移的矩阵
但是这周是k*N,状态矩阵不好手算,都是我们改成用程序自动生成一个状态转移的矩阵就行了,然后用这个矩阵进行快速幂即可
枚举枚举上下两行的状态,然后判断上一行的状态能不能转移为这一行的状态
如果上一行的某个位置为0,那么这一行的该位置必须为1
如果上一行的某个位置为1,那么这一行的该位置可以为0
如果上一行的某个位置为1,且这一行的该位置为1, 那么上下两行该位置相邻的位置也得为1
根据这三条规则判断状态能不能转移成功,然后生成矩阵
因为状态矩阵很大,不能够开成局部变量,所以一律开成全局的,函数的返回值全部改成void
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = << ;
const int MOD = ;
const int N = << ;
int n, k;
struct Matrix
{
int mat[N][N];
void makeUnit()
{
int m = ( << k);
for (int i = ; i < m; ++i)
{
for (int j = ; j < m; ++j)
mat[i][j] = (i == j);
}
}
void makeZero()
{
int m = << k;
for (int i = ; i < m; ++i)
{
for (int j = ; j < m; ++j)
mat[i][j] = ;
}
}
}a, ret1, ret2;
void copy(Matrix &des, const Matrix &s)
{
int m = << k;
for (int i = ; i < m; ++i)
{
for (int j = ; j < m; ++j)
des.mat[i][j] = s.mat[i][j];
}
}
void dfs(int x, int y, int col)//这个题目提示的矩阵生成方法,挺厉害的
{
if (col == k)
{
a.mat[y][x] = ;
return;
}
dfs(x << , y << | , col + );
dfs(x << | , y << , col + );
if (col + <= k)
dfs((x << ) + , (y << ) + , col + );
}
void multiply(const Matrix &lhs, const Matrix &rhs)
{
ret2.makeZero();
int m = << k;
for (int z = ; z < m; ++z)
{
for (int i = ; i < m; ++i)
{
if (lhs.mat[i][z] == ) continue;
for (int j = ; j < m; ++j)
{
ret2.mat[i][j] += lhs.mat[i][z] * rhs.mat[z][j];
if (ret2.mat[i][j] >= MOD)
ret2.mat[i][j] %= MOD;
}
}
}
}
void pow(Matrix a, int t)
{
ret1.makeUnit();
while (t)
{
if (t & )
{
multiply(ret1, a);
copy(ret1, ret2);
}
t >>= ;
multiply(a, a);
copy(a, ret2);
}
}
bool check(int x, int y)
{
int m = << k-;
while (m)
{
if ((x & ) == && (y & ) == )
{
x >>= ;
y >>= ;
m >>= ;
}
else if ((x & ) == && (y & ) == )
{
x >>= ;
y >>= ;
m >>= ;
}
else if ((x & ) == && (y & ) == )
{
x >>= ;
y >>= ;
if ((x & ) == && (y & ) == )
{
x >>= ;
y >>= ;
m >>= ;
}
else
return false;
}
else
return false;
}
return true;
}
void makeMatrix()
{
int m = << k;
for (int i = ; i < m; ++i)
{
for (int j = ; j < m; ++j)
{
if (check(i, j))
a.mat[i][j] = ;
}
}
}
int main()
{
scanf("%d%d", &k, &n);
a.makeZero();
//dfs(0, 0, 0);
makeMatrix();
pow(a, n);
int m = ( << k) - ;
printf("%d\n", ret1.mat[m][m]);
return ;
}