题意
有⼀排阶梯，每列的⾼度不减，且是 $1$ 到 $7$ 的整数，⾼度为 $i$ 的阶梯有 $w_i$ 个，现在你需要给阶梯的某些边缘上⾊，要求边缘必须上⾊，且不能框出 $1∗1$ 的⼩正⽅形。求⽅案数对 $10^9+7$ 取模。
题解
每列的高度只能是1-7，这个数字很小，那么可以将每列上色情况用二进制表示。只记录中间的横边及右侧的竖边即可开始转移。
| 假如记有颜色的为0，没颜色的为1，记左侧（上一列右侧）为 $i$，右侧为 $j$，中间的为 $k$，那么可发现如果 $i | j | k | k«1 == 全1$，则成立。 |
把 $i,j$ 作为矩阵行列，个数放入转移矩阵，ksm一下就可以啦。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int matn;
const int mod=1e9+7;
struct matrix{
int a[150][150];
matrix operator* (const matrix &o) const;
matrix operator^ (int p) const;
}one;
matrix matrix::operator* (const matrix &o) const{
matrix res;
for(int i=0;i<matn;++i)
for(int j=0;j<matn;++j){
res.a[i][j]=0;
for(int k=0;k<matn;++k)
(res.a[i][j]+=(ll)a[i][k]*o.a[k][j]%mod)%=mod;
}
return res;
}
matrix matrix::operator^ (int p) const{
matrix res=one,cp=*this;
while(p){
if(p&1)res=res*cp;
cp=cp*cp;
p>>=1;
}
return res;
}
int main(){
for(int i=0;i<128;++i)one.a[i][i]=1;
matrix res=one;
for(int t=1,x;t<=7;++t){
matn=1<<t;
matrix tmp;
int tot=1<<t;
scanf("%d",&x);
for(int i=0;i<tot;++i){
for(int j=0;j<tot;++j){
tmp.a[i][j]=0;
for(int tt=0;tt<(1<<(t-1));tt++){
if((i|j|tt|(tt<<1)) == tot-1) tmp.a[i][j]++;
}
}
}
res=res*(tmp^x);
}
printf("%d",res.a[0][0]);
}