经典的状态 DP 结合矩阵快速幂题。
- \(N \le 8\)，我们可以状态压缩。每一列最多只有 \(2^8 = 256\) 种状态。
- \(M \le 10^{18}\)，我们可以将转移方程构建成一个转移矩阵，用矩阵快速幂在 \(O(\log M)\) 的复杂度内求解。
我们按列从左到右填。对于第 \(i\) 列，我们定义一个 \(N\) 位的二进制数 \(S\)：
- 如果 \(S\) 的第 \(j\) 位为 \(1\)，表示第 \(i\) 列的第 \(j\) 行被前一列 \(1 \times 2\) 延伸过来占用了。
- 如果 \(S\) 的第 \(j\) 位为 \(0\)，表示第 \(i\) 列的第 \(j\) 行是空的，需要我们在当前列去填充。
设当前列的初始状态为 \(S\)，我们需要填满当前列的空位，并推导出对下一列的初始状态 \(T\)。
- 若 \(S\) 对应位为 \(1\)，即当前格子已经被占用，什么都不能放，对应 \(T\) 的这一位一定为 \(0\)。
- 若 \(S\) 对应位为 \(0\)，即当前格子是空的，我们必须把它填满，有 \(3\) 种选择：
- \(2 \times 1\)（条件是当前格子和它下面的格子都是空的）：占用当前格子和它下面的格子。这两个格子都不会延伸到下一列，对应 \(T\) 的这一位和下一位都是 \(0\)。
- \(1 \times 2\)：占用当前格子和下一列的同一个格子，对应 \(T\) 的这一位为 \(1\)。
- \(1 \times 1\)：占用当前格子，对应 \(T\) 的这一位为 \(0\)。
转移矩阵可以预处理。
答案是 \(M^N[0][0]\)。
:::info[Code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1<<8;
const int mod=1e9;
struct matrix{int n,m;int a[N][N];matrix(){n=m=0;memset(a,0,sizeof(a));return;}void idtt(){memset(a,0,sizeof(a));for(int i=0;i<n;i++)a[i][i]=1;return;}void print(){for(int i=0;i<n;i++,cout<<'\n')for(int j=0;j<m;j++)cout<<a[i][j]<<' ';return;}
}g;
matrix operator * (const matrix& x,const matrix& y){assert(x.m==y.n);matrix res;res.n=x.n,res.m=y.m;for(int k=0;k<x.m;k++)for(int i=0;i<x.n;i++)for(int j=0;j<y.m;j++)res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%mod;return res;
}
matrix qpow(matrix x,int y){matrix res=x;res.idtt();while(y){if(y&1) res=res*x;x=x*x;y>>=1;}return res;
}
int n,m;
signed main(){// freopen("in.in","r",stdin);// freopen("out.out","w",stdout);cin>>n>>m;g.n=g.m=(1<<n);for(int i=0;i<(1<<n);i++){vector<int> nxt(1),to;for(int j=0;j<n;j++){if(i&(1<<j))continue;vector<int> nw;nw.swap(to);for(int u:nxt){if(j+1<n&&(i&(1<<(j+1)))==0)to.push_back(u);nw.push_back(u+(1<<j));nw.push_back(u);}nxt.swap(nw);}for(int u:nxt)g.a[i][u]++;}// g.print();cout<<qpow(g,m).a[0][0];return 0;
}
:::