50pts求调

#include <bits/stdc++.h>
#define pb push_back
#define pf(a) push_front(a)
#define pof pop_front
#define pob pop_back
#define fr() front()
#define ba() back()
#define ls(x) x << 1
#define rs(x) (x << 1) | 1
#define re register
#define in(a) insert(a)
#define fi first
#define se second
#define gcd(a, b) __gcd(a, b)
#define l2(a) log(a) / log(2)
#define ui128 unsigned __int128
#define int long long
#define pll pair<ll, ll>
#define ull unsigned long long
#define pii pair<int, int>
#define pq1 priority_queue<int>
#define pq2 priority_queue<int, vector<int>, greater<int>>
#define ui unsigned int
#define db double
#define Add1(u,v) g[u].pb(v)
#define Add2(u,v,w) g[u].pb({v,w})
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
const int N = 1000006, M = 6;
const int mod = 1ll << 32;
int n, m, p, K, len, siz;
int att[3];
vector<int> fst;
int cal(int x, int p, int ik) {
    if(p <= ik) return x << (ik - p);
    return x >> (p - ik);
}
bool check(int x) {
    int tmp = x;
    for(int i = 0; tmp >> i; ++i) {
        if((x & (1 << i)) == 0) continue;
        if((x & cal(att[1], p, i + K)) & ((len - 1) ^ (1 << i))) return false;
    }
    return true;
}

bool con(int x, int y) {
    x ^= y ^= x ^= y;
    int tmp = x;
    for(int i = 0; i < m; ++i) {
        if((x & (1 << i)) == 0) continue;
        if(y & cal(att[2], p, i + K)) return false;
    }     
    tmp = y;
    for(int i = 0; i < m; ++i) {
        if((y & (1 << i)) == 0) continue;
        if(x & cal(att[0], p, i + K)) return false;
    }    
    return true;
}

struct matrix {
    int m[(1 << M) + 5][(1 << M) + 5], a, b;
    matrix(int x, int y) {
        a = x; b = y;
        for(int i = 1; i <= a; ++i)
            for(int j = 1; j <= b; ++j)
                m[i][j] = 0;
    }
    matrix friend operator * (matrix x, matrix y) {
        matrix ans(x.a, y.b);
        for(int i = 1; i <= x.a; ++i)
            for(int k = 1; k <= y.a; ++k) {
                int s = x.m[i][k];
                for(int j = 1; j <= y.b; ++j)
                    ans.m[i][j] = (ans.m[i][j] + s * y.m[k][j] % mod) % mod;
            }
        return ans;
    }
};

matrix ksm(matrix base, int p) {
    matrix res(siz, siz);
    for(int i = 1; i <= siz; ++i) res.m[i][i] = 1;
    while(p) {
        if(p & 1) res = base * res;
        base = base * base; p >>= 1;
    }
    return res;
}   

signed main() {
    IOS;
    cin >> n >> m >> p >> K; ++K;
    len = 1 << m;
    for(int i = 0; i < 3; ++i)
        for(int j = 1, tmp; j <= p; ++j)
            att[i] <<= 1, cin >> tmp, att[i] |= tmp;
    fst.pb(0x7fffffff);
    for(int i = 0; i < len; ++i)
        if(check(i)) fst.pb(i);
    siz = fst.size() - 1; 
    matrix zy(siz, siz);
    for(int i = 1; i <= siz; ++i) 
        for(int j = 1; j <= siz; ++j)
            if(con(fst[i], fst[j])) zy.m[i][j] = 1;
    matrix res = ksm(zy, n - 1);
    int ans = 0;
    for(int i = 1; i <= siz; ++i)
        for(int j = 1; j <= siz; ++j)
            (ans += res.m[i][j]) %= mod;
    cout << ans;
    return 0;
}