模拟赛场切紫，来水题解。

注意到 $m\le6$，因此考虑状压 dp。对每一行进行状压，设 $f_{i,s}$ 表示第 $i$ 行，棋子的状态为二进制串 $s$ 的方案数。设 $\operatorname{check}(s1,s2)$ 表示上一行棋子状态为 $s1$，下一行为 $s2$ 是否不会产生冲突。那么我们可以写出状态转移方程：

$$\displaystyle f_{i,s2}=\sum_{s1\land \operatorname{check}(s1,s2)} f_{i-1,s1}$$

时间复杂度 $O(n2^{2m})$，期望得分 $50$。我试了一下如果只枚举合法的 $(s1,s2)$，在模拟赛数据下可以通过，但是洛谷被卡空间了，你可以试试看能不能过。

注意到 $f_i$ 的转移都是相同的，因此考虑矩阵快速幂优化。我们需要把 $\begin{bmatrix} f_{i-1,0} \\ f_{i-1,1} \\ \vdots \\ f_{i-1,2^m-1} \end{bmatrix}$ 乘上一个东西，得到 $\begin{bmatrix} f_{i,0} \\ f_{i,1} \\ \vdots \\ f_{i,2^m-1} \end{bmatrix}$ 。转移矩阵如果放在后面的话，第一行乘以第一列，就会得到一堆 $f_{i-1,0}$。这并不是我们想要的。因此转移矩阵要放在前面。手玩一下，转移矩阵就变成了把合法的 $(s2,s1)$ 置为 $1$，其他为 $0$。接着矩阵快速幂转移即可。

最后注意 $\operatorname{check}$ 函数的实现，二进制串是从右往左读的，而棋子的控制范围是从左往右读的，因此要记得翻转其中之一。

#include<bits/stdc++.h>
#define int unsigned int
#define N 1000005
#define M 6
using namespace std;
struct Matrix
{
	int n,m,a[1<<M][1<<M];
	void clear()
	{
		memset(a,0,sizeof(a));
		return;
	}
}st,tmp;
int n,m,p,k,x,ans,f[N][1<<M];
vector<int>v[1<<M];
bool a[3][M],b[2][M];
Matrix operator*(Matrix x,Matrix y)
{
	Matrix z;
	z.n=x.n,z.m=y.m;
	z.clear();
	for(int i=0;i<(1<<m);i++) for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) z.a[i][j]+=x.a[i][k]*y.a[k][j];
	return z;
}
Matrix Pow(Matrix x,int y)
{
	Matrix z;
	z.n=z.m=x.n;
	memset(z.a,0,sizeof(z.a));
	for(int i=0;i<z.n;i++) z.a[i][i]=1;
	while(y)
	{
		if(y&1) z=z*x;
		x=x*x;
		y>>=1;
	}
	return z;
}
bool check(int s1,int s2)
{
	memset(b,0,sizeof(b));
	for(int i=0;i<m;i++) if(s1&(1<<i)) for(int j=0;j<p;j++) if(m-i-1+j-k>=0&&m-i-1+j-k<m) b[0][m-i-1+j-k]|=a[1][j],b[1][m-i-1+j-k]|=a[2][j];
	for(int i=0;i<m;i++) if(s2&(1<<i)) for(int j=0;j<p;j++) if(m-i-1+j-k>=0&&m-i-1+j-k<m) b[0][m-i-1+j-k]|=a[0][j],b[1][m-i-1+j-k]|=a[1][j];
	for(int i=0;i<m;i++) if(((s1&(1<<i))&&b[0][m-i-1])||((s2&(1<<i))&&b[1][m-i-1])) return 0;
	return 1;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m>>p>>k;
	for(int i=0;i<3;i++) for(int j=0;j<p;j++) cin>>a[i][j];
	a[1][k]=0;
	tmp.n=tmp.m=(1<<m);
	for(int s1=0;s1<(1<<m);s1++) for(int s2=0;s2<(1<<m);s2++) if(check(s1,s2)) v[s1].push_back(s2),tmp.a[s2][s1]=1;
	st.n=(1<<m),st.m=1;
	for(int now:v[0]) st.a[now][0]=1;
	tmp=Pow(tmp,n-1);
	st=tmp*st;
	for(int i=0;i<(1<<m);i++) ans+=st.a[i][0];
	cout<<ans;
	return 0;
}