算法

三进制状压DP，需要预处理出合法的状态

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N = 10010, M = 330, MOD = 1e6;

int w[N][M];
int n, m;
int K;
int sk;

int stat[M], cnt;
int s2id[1 << 10];

int get(int s, int k)
{
    return (s >> 2 * k) & 3;
}

bool check(int s1, int s2)
{
    int s3 = s1 ^ s2;
    for(int i = 0; i < m; ++ i)
        if(!get(s3, i))
            return false;
    return true;
}

int main()
{
    scanf("%d %d", &n, &m);
    scanf("%d", &K);
    for(int i = 0; i < m; ++ i)
    {
        int x;
        scanf("%d", &x);
        sk += (x << 2 * i);
    }

    bool lg = true;
    for(int j = 0; j < m; ++ j)
    {
        int a = get(sk, j), b = get(sk, j - 1), c = get(sk, j + 1);
        if(!a) lg = false;
        if(j && !b) lg = false;
        if(j < m - 1 && !c) lg = false;
        if(!j && a == c) lg = false;
        if(j == m - 1 && a == b) lg = false;
        if(j && j < m - 1 && ((a == b) || (a == c))) lg = false;
        if(lg == false) break;
    }

    if(!lg) 
    {
        printf("%d", 0);
        return 0;
    }

    for(int i = 0; i < 1 << m * 2; ++ i)
    {
        bool lg = true;
        for(int j = 0; j < m; ++ j)
        {
            int a = get(i, j), b = get(i, j - 1), c = get(i, j + 1);
            if(!a) lg = false;
            if(j && !b) lg = false;
            if(j < m - 1 && !c) lg = false;
            if(!j && a == c) lg = false;
            if(j == m - 1 && a == b) lg = false;
            if(j && j < m - 1 && ((a == b) || (a == c))) lg = false;
            if(lg == false) break;
        }
        if(lg) stat[cnt ++ ] = i, s2id[i] = cnt - 1;
    }

    w[0][s2id[sk]] = 1;

    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < cnt; ++ j)
        {
            int sj = stat[j];
            for(int u = 0; u < cnt; ++ u)
            {
                int su = stat[u];
                if(check(sj, su)) w[i + 1][u] = (w[i + 1][u] + w[i][j]) % MOD;
            }
        }
    int res1 = 0, res2 = 0;
    for(int i = 0; i < cnt; ++ i) res1 = (res1 + w[K - 1][i]) % MOD;
    for(int i = 0; i < cnt; ++ i) res2 = (res2 + w[n - K][i]) % MOD;
    int res = ((LL)res1 * res2) % MOD;
    printf("%d", res);
    return 0;
}