题目链接

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
typedef unsigned int ui;
const int maxn=1e6+7;
const int maxs=1<<7;
int n,m,p,k,lane[5];
ui f[maxs];
struct martix{
	ui data[65][65];
	inline void reset(){
		for(int i=0;i<=64;i++)
			for(int j=0;j<=64;j++)
				data[i][j]=0;
	}
	inline void unit(){
		reset();
		for(int i=0;i<=64;i++)
			data[i][i]=1;
	}
	inline martix operator*(martix arg){
		martix res;
		res.reset();
		for(int i=0;i<=64;i++)
			for(int j=0;j<=64;j++)
				for(int k=0;k<=64;k++)
					res.data[i][j]+=data[i][k]*arg.data[k][j];
		return res;
	}
	inline ui* operator[](int id){
		return data[id];
	}
	inline ui summary(){
		ui sum=0;
		for(int i=0;i<=64;i++)
			for(int j=0;j<=64;j++)
				sum+=data[i][j];
		return sum;
	}
}F,ANS;
inline martix fastpow(martix E,int k){
	martix res;
	res.unit();
	while(k){
		if(k&1)
			res=res*E;
		E=E*E;
		k>>=1;
	}
	return res;
}
int sc;
int main(){
	#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	#endif
	scanf("%d%d%d%d",&n,&m,&p,&k);
	int x;
	for(int i=0;i<3;i++){
		for(int j=0;j<p;j++){
			scanf("%d",&x);
			if(x)
				lane[i]|=1<<j;
		}
	}
	ui STAT=(1<<m)-1;
	for(ui A=0;A<=STAT;A++){
		bool ok=true;
		for(int i=0;i<p;i++){
			if(i==k)
				continue;
			if(lane[1]&(1<<i)){
				if(i<k){
					if((A>>(k-i))&A){
						ok=false;
						break;
					}
				}else{
					if((A<<(i-k))&A){
						ok=false;
						break;
					}
				}
			}
		}
		if(ok){
			f[A]=1;
			sc++;
		}
	}
	return sc;
	F.reset();
	for(ui A=0;A<=STAT;A++)
		for(ui B=0;B<=STAT;B++){
			if(!f[A]||!f[B])
				continue;
			bool ok=true;
			for(int i=0;i<p;i++){
				if(lane[0]&(1<<i)){
					if(i<k){
						if((A>>(k-i))&B){
							ok=false;
							break;
						}
					}else{
						if((A<<(i-k))&B){
							ok=false;
							break;
						}
					}
				}
				if(lane[2]&(1>>i)){
					if(i<k){
						if((B>>(k-i))&A){
							ok=false;
							break;
						}
					}else{
						if((B<<(i-k))&A){
							ok=false;
							break;
						}
					}
				}
			}
			if(!ok)
				continue;
			F[A][B]=1;
		}
	ANS.reset();
	for(int i=0;i<=STAT;i++)
		if(f[i])
			ANS[1][i]=1;
	n--;
	F=fastpow(F,n);
	ANS=ANS*F;
	printf("%u",ANS.summary());
	return 0;
}