状压\(DP\)加矩阵优化。
关于这道题的出题人。。。
他当年应该被打死了吧。。。
题目中的第\(1\)行第\(k\)列指的是从\(0\)开始标号下的第\(1\)行第\(k\)列，也就是说，这一题存在第\(0\)行第\(0\)列！
搞什么不好，非得要搞题意理解。。。
设\(f[i][j]\)为第\(i\)行，状态为\(j\)时的答案（我们只压了一行）。
如果\(j\)可以转移到\(k\)，则有\(f[i+1][k]=f[i][j]+f[i+1][k]\)。
这里我们发现，两个集合是否可以转移，这是固定的，也就是说，我们可以矩阵快速幂优化一下。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int f=1,w=0;char x=0;
while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
return w*f;
}
const int M=7;
const int p=1LL<<32;
const int N=1e6+10;
int n,m,K,C,Max,ans,f[1<<M];
vector<int> Atk[3];
struct Matrix
{
int A[80][80];
inline Matrix (){ memset(A,0,sizeof(A));}
inline Matrix operator * (const Matrix &B) const
{
Matrix C;
for(register int i=0;i<Max;++i)
for(register int j=0;j<Max;++j)
for(register int k=0;k<Max;++k)
C.A[i][j]=(C.A[i][j]%p+(A[i][k]*B.A[k][j])%p+p)%p;
return C;
}
} Trn;
inline Matrix ksm(Matrix b,int k)
{
Matrix a=b;k--;
while(k)
{
if(k&1) a=a*b;
b=b*b;k>>=1;
}
return a;
}
inline bool Check(int x,int y)
{
for(register int i=0;i<m;++i)
if((x>>i)&1)
{
for(register int j=0;j<(int)Atk[1].size();++j)
if(0<=i+Atk[1][j]&&i+Atk[1][j]<m)
if((x>>(i+Atk[1][j]))&1) return 0;
for(register int j=0;j<(int)Atk[2].size();++j)
if(0<=i+Atk[2][j]&&i+Atk[2][j]<m)
if((y>>(i+Atk[2][j]))&1) return 0;
}
for(register int i=0;i<m;++i)
if((y>>i)&1)
{
for(register int j=0;j<(int)Atk[1].size();++j)
if(0<=i+Atk[1][j]&&i+Atk[1][j]<m)
if((y>>(i+Atk[1][j]))&1) return 0;
for(register int j=0;j<(int)Atk[0].size();++j)
if(0<=i+Atk[0][j]&&i+Atk[0][j]<m)
if((x>>(i+Atk[0][j]))&1) return 0;
}
return 1;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
n=read(),m=read(),C=read(),K=read();Max=1LL<<m;
for(register int i=0;i<3;++i)
for(register int j=0;j<C;++j)
if(read()&&(j!=K||i!=1)) Atk[i].push_back(j-K);
for(register int i=0;i<Max;++i)
for(register int j=0;j<Max;++j)
Trn.A[i][j]=Check(i,j);
for(register int i=0;i<Max;++i) f[i]=Trn.A[0][i];Trn=ksm(Trn,n);
for(register int i=0;i<Max;++i) ans=(ans%p+(f[i]%p*Trn.A[i][0]%p+p)%p+p)%p;
printf("%lld",(ans+p)%p);
}