我一上来打了个傻乎乎的状压。。成功TLE 50%（不要阻止我装sb。。）
其实这道题叙述有点问题，给的那个3*p的矩阵，第一行是第0行。。。那么就发现转移只跟自己上一行的状态有关，但n太大了，而状态很少，少到能写进一个矩阵，快速幂get。
只要构造出f[i][j],i状态能转移到j状态，则f[i][j]=1;
把这个矩阵自乘n次即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll unsigned long long
#define mod (ll)4294967296
using namespace std;
int n,m,p,k,tot,w[4],xp[10],g[65];
ll sum;
struct node
{
ll f[65][65];
friend node operator *(node a,node b)
{
node c;memset(c.f,0,sizeof(c,f));
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
for(int k=1;k<=tot;k++)
{
c.f[i][j]+=(a.f[i][k]*b.f[k][j])%mod;
if(c.f[i][j]>=mod)c.f[i][j]-=mod;
}
return c;
}
}ans,h;
inline void check(int x,int y)
{
for(int i=1;i<=m;i++)if(xp[i-1]&g[x])
{
int j=i-k;
if(j>=0){if((w[3]<<j)&g[y])return;}
else{j=-j;if((w[3]>>j)&g[y])return;}
}
for(int i=1;i<=m;i++)if(xp[i-1]&g[y])
{
int j=i-k;
if(j>=0){if((w[1]<<j)&g[x])return;}
else{j=-j;if((w[1]>>j)&g[x])return;}
}
h.f[x][y]=1;
}
inline void get(int x)
{
for(int i=1;i<=m;i++)if(xp[i-1]&x)
{
int j=i-k;
if(j>=0){if((w[2]<<j)&x)return;}
else{j=-j;if((w[2]>>j)&x)return;}
}
g[++tot]=x;
}
int yjn()
{
scanf("%d%d%d%d",&n,&m,&p,&k);k++;
int x;xp[0]=1;
for(int i=1;i<=10;i++)xp[i]=xp[i-1]*2;
for(int i=1;i<=3;i++)
for(int j=1;j<=p;j++)
{
scanf("%d",&x);if(i==2&&j==k)continue;
if(x)w[i]|=xp[j-1];
}
for(int i=0;i<xp[m];i++)get(i);
for(int i=1;i<=tot;i++)
for(int j=1;j<=tot;j++)
check(i,j);
for(int i=1;i<=tot;i++)ans.f[i][i]=1;
while(n)
{
if(n&1)ans=ans*h;
h=h*h;
n/=2;
}
for(int i=1;i<=tot;i++)sum=(sum+ans.f[1][i])%mod;
cout<<sum%mod;
}
int qty=yjn();
int main(){;}