Description：

$n$ 行 $m$ 列的棋盘，每个棋子的攻击范围是 $3$ 行 $p$ 列的模板，棋子在第 $1$ 行第 $k$ 列。求棋子互相不能攻击到的前提下摆放棋子的方案数。

$1\le n \le 10^6,1\le m \le 6$

Solution：

$n$ 这么大 $m$ 这么小看着是个在 $m$ 方向上状压，在 $n$ 方向上递推，刚开始认为要压两行所以一直没想出正解，但是发现虽然会有两行交叉，但只有一行的状态会决定转移，也就是说当前这一行虽然会受上一行影响，但是是由上一行决定的，只要记录上一行就可以确定状态，然后就预处理合法状态及转移，然后矩阵快速幂。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int n,m;

int l,p;

typedef unsigned int uint;

typedef long long ll;

#define MAXN 1000010

ll tot;

struct matrix

{

    unsigned int m[70][70];

    matrix(){memset(m,0,sizeof(m));}

    friend matrix operator * (matrix a,matrix b)

    {

        matrix c;

        for(int i = 0;i <= tot;++i)

            for(int j = 0;j <= tot;++j)

                for(int k = 0;k <= tot;++k)

                    c.m[i][j] += a.m[i][k] * b.m[k][j];

        return c;

    }

    friend matrix operator ^ (matrix a,int b)

    {

        matrix res = a;--b;

        while(b > 0)

        {

            if(b & 1)res = res * a;

            a = a * a;

            b = b >> 1;

        }

        return res;

    }

}f;

ll temp[4];

ll blo[70][4];

bool ava[70];

int main()

{

    scanf("%d%d",&n,&m);

    scanf("%d%d",&l,&p);

    for(int i = 1;i <= 3;++i)

        for(int j = l;j >= 1;--j)

            temp[i] |= (read() << (j - 1));

    temp[2] ^= (1 << (l - p - 1));

    tot = (1 << m) - 1;

    for(ll b = 0;b <= tot;++b)

    {

        for(int i = 1;i <= 3;++i)

        {

            ll tmp = 0;

            for(ll k = m - 1;k >= 0;--k)

            {

                if((b >> k) & 1)

                {

                    if(k >= (l - p - 1))tmp |= ((temp[i] << (k - (l - p - 1))) & tot);

                    else tmp |= (temp[i] >> (l - p - 1 - k));

                }

            }

            blo[b][i] = tmp;

        }

        ava[b] = true;

        for(int i = 0;i < m;++i)

            if((blo[b][2] & (1 << i)) && (b & (1 << i)))

                ava[b] = false;

    }

    for(int i = 0;i <= tot;++i)

        if(ava[i])

            for(int j = 0;j <= tot;++j)

                if(ava[j])

                    if((blo[i][3] & j) == 0 && (i & blo[j][1]) == 0)

                        f.m[i][j] = 1;

    --n;

    f = f ^ n;

    unsigned int ans = 0;

    for(int i = 0;i <= tot;++i)

        for(int j = 0;j <= tot;++j)

            ans += f.m[i][j];

    printf("%u\n",ans);

    return 0;

}