记录编号	162623	评测结果	AAAAAAAAAA
题目名称	[TJOI 2015] 棋盘	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2015-05-18 11:29:58	内存使用	0.31 MiB

/*************************************************************************/
/****************************Designed By Asm.Def**************************/
/*************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
//#define FREAD

#define FREADLENTH 5000000
#ifdef FREAD
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 1 << 6;
typedef unsigned uint;

int N, M, p, k, n;
uint T[3];

struct Mat{uint A[maxn][maxn];}F;
inline Mat operator * (const Mat &a, const Mat &b){
	Mat Ans = {{0}};
	int i, j, k;
	for(i = 0;i < n;++i)for(j = 0;j < n;++j)for(k = 0;k < n;++k)
		Ans.A[i][j] += a.A[i][k] * b.A[k][j];
	return Ans;
}
inline Mat pow(Mat a, int n){
	--n;
	Mat Ans = a;
	while(n){
		if(n & 1)Ans = Ans * a;
		a = a * a;
		n >>= 1;
	}
	return Ans;
}

inline void init(){
	getd(N), getd(M), getd(p), getd(k);
	int i, j, ch;
	n = 1 << M;
	for(i = 0;i < 3;++i)for(j = 0;j < p;++j){
		getd(ch);
		T[i] |= (ch << j);
	}
}

inline bool calc(int a, int b, uint t){
	int i;
	uint tmp = t << (M - 1 - k);
	bool ans = true;
	for(i = M-1;i >= 0;--i, tmp >>= 1)
		ans &= (!((a & (1u << i)) && (b & tmp)));
	return ans;
}

inline void work(){
	int i, j;
	unsigned tmp;
	bool ok[maxn] = {1, 0};
	for(i = 1;i < n;++i){
		ok[i] = true;
		tmp = T[1] << (10 - k);
		for(j = 0;j < M;++j)
			ok[i] &= (!((i & (1 << j)) && ((i & (tmp >> (10-j))) != (1u << j))));
	}
	for(i = 0;i < n;++i)if(ok[i])for(j = 0;j < n;++j)if(ok[j])
		F.A[i][j] = calc(i, j, T[2]) & calc(j, i, T[0]);
	F = pow(F, N);
	uint ans = 0;
	for(i = 0;i < n;++i)ans += F.A[0][i];
	printf("%u\n", ans);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#else
	SetFile(tjoi2015_board);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif

	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}