前制知识引导
状态压缩动态规划：[P1896 [SCOI2005] 互不侵犯](https://www.luogu.com.cn/problem/P1896)
矩阵加速优化：[P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962)
---
### 1.抓住数据范围的特点列出 dp 方程。
由于 $m\le6$，很容易想到利用状态压缩解决问题。
用一个 $6$ 位的二进制数存储每一行的状态，很容易能列出状态转移方程。
$\mathit{dp}_{i,j}=\sum_{k=1}^{(1<<m)-1} (\mathit{dp}_{i-1,k})$，其中 $k$ 与 $j$ 不能互相攻击。
-----
### 2.找到合法方案
我们先得找到能使本行合理的二进制数。
例如一个棋子本行攻击模板为 $1011$，$k=2$。
那么有一个在第 $0$ 列，距离 $k$ 差两个单位距离。
那么等价于不能有两个 $1$ 相隔距离为 $2$。
所以当二进制数 $j$ 满足 $(j\land(j<<2))=0$ 时合法。
由于棋子在模板中的第一行，所以处理不同行的两个二进制数要分从上往下和从下往上。
考虑暴力枚举。每遇到一个下方二进制数 $j$ 的 $1$ 时，在上方进行枚举，
当遇到下方的 $1$ 能攻击上方的 $1$ 时，方案不合法。从上往下同理。
总复杂度 $O(n \times 2^{m^2} )$。
-----
### 3.矩阵快速幂优化
上面复杂度明显不能过掉本题，所以考虑优化。
对于每一次 dp 转移，每一个 $j$ 都对应着固定的多个 $k$，并且每次转移重复做着求和工作。
那么就可以考虑矩阵优化。
建立一个 $m^2\times 1$ 的初始矩阵与一个 $m^2\times m^2$ 的转移矩阵。
对于初始矩阵的每一位 $(j,1)$，如果 $j$ 符合本行方案，那么赋值为 $1$,否则赋为 $0$。
对于转移矩阵的每一位 $(j,k)$，若 $j$ 与 $k$ 互不侵犯，则赋为 $1$,否则赋为 $0$。
最后对于初始矩阵进行 $(n-1)$ 的重复求积，可以利用快速幂解决。
时间复杂度为 $O(2^{m^3}\times \log(n))$。
---
### 4.细节处理
由于模数为 $2^{32}$ 过大，需用龟速乘。
但毕竟已经允许用 __int128 了，所以就偷个懒吧。
```cpp
#include<iostream>
#include<cstdio>
#define int __int128
using namespace std;
const int M=6;
int n,m,p,k,mod=1,t[5][10],vis[1<<M];
inline int read()
{
char ch=getchar();
int f=1,sum=0;
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
sum=(sum<<1)+(sum<<3)+(ch-48);
ch=getchar();
}
return sum*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x/10)write(x/10);
putchar(x%10+'0');
}
void take_spc()
{
for(int i=0;i<1<<m;i++)
{
vis[i]=1;
for(int j=1;j<=p;j++)
{
if(t[2][j])
{
if(j<k&&(i&(i<<(k-j))))vis[i]=0;
if(j>k&&(i&(i>>(j-k))))vis[i]=0;
}
}
}
}
struct matrix
{
int a[1<<M+1][1<<M+1],x,y;
void init()
{
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
a[i][j]=0;
}
}
}
}u,v;
matrix operator *(matrix fi,matrix se)
{
matrix th;
th.x=fi.x,th.y=se.y;
th.init();
for(int i=1;i<=fi.x;i++)
{
for(int j=1;j<=se.y;j++)
{
for(int p=1;p<=fi.y;p++)
{
th.a[i][j]+=fi.a[i][p]*se.a[p][j]%mod;
th.a[i][j]%=mod;
}
}
}
return th;
}
bool check(int fi,int se)
{
if(!vis[fi]||!vis[se])return false;
for(int i=0;i<m;i++)
{
if(fi&(1<<i))
{
for(int j=i-k+2,pt=1;j<=i+p-k+1;j++,pt++)
{
if(j<1||j>m)continue;
if(t[3][pt]&&((1<<(j-1))&se))return false;
}
}
}
for(int i=0;i<m;i++)
{
if(se&(1<<i))
{
for(int j=i-k+2,pt=1;j<=i+p-k+1;j++,pt++)
{
if(j<1||j>m)continue;
if(t[1][pt]&&((1<<(j-1))&fi))return false;
}
}
}
return true;
}
void quick_pow(int num)
{
while(num)
{
if(num&1)v=u*v;
u=u*u;
num>>=1;
}
}
signed main()
{
for(int i=1;i<=32;i++)mod*=2;
n=read(),m=read(),p=read(),k=read();
k++;
for(int i=1;i<=3;i++)for(int j=1;j<=p;j++)t[i][j]=read();
take_spc();
u.x=1<<m,u.y=1<<m,u.init();
v.x=1<<m,v.y=1,v.init();
u.x=1<<m,v.y=1;
for(int i=0;i<1<<m;i++)if(vis[i])v.a[i+1][1]=1;
for(int i=0;i<1<<m;i++)
{
for(int j=0;j<1<<m;j++)
{
if(check(i,j))u.a[i+1][j+1]=1;
}
}
quick_pow(n-1);
int ans=0;
for(int i=1;i<=1<<m;i++)ans+=v.a[i][1],ans%=mod;
write(ans);
return 0;
}
```