题目描述

$这题需要转化为三进制，然后从k往前dp，再从k往后dp，两个方案数相乘即是答案。$

算法1

C++ 代码

#include<cstdio>
using namespace std;
const int N = 1e4 + 1;
const int mod = 1e6;
#define ll long long
ll dp[N][251];
ll mp[N];
ll n, m, k, cnt;
ll sta;
ll st[N];
bool check(ll a){
    ll tmp = -1, last = -1;
    for(int i = 1;i <= m;i ++){
        tmp = a % 3;
        if(tmp == last)
        return false;
        last = tmp;
        a /= 3;
    }
    return true;
}
ll qmi(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a;
        a = 1ll * a * a;
        b >>= 1;
    }
    return res;
}
bool judge(ll a, ll b){
    for(int i = 1;i <= m;i ++){
        if(a % 3 == b % 3) return false;
        a /= 3;
        b /= 3;
    }
    return true;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i = 1;i <= m;i ++){
        scanf("%lld",&mp[i]);
        sta = sta * 3 + mp[i] - 1;
    }
    ll maxx = qmi(3, m);
    cnt = 0;
    for(int i = 0;i < maxx;i ++){
        if(check(i))
        st[++cnt] = i;
    }
    ll pos = -1;
    for(int i = 1;i <= cnt;i ++){
        if(st[i] == sta){
            pos = i;
            break;
        }
    }
    if(pos == -1){
        puts("0");
        return 0;
    }
    dp[k][pos] = 1;
    for(int i = k - 1;i >= 1;i --)
    for(int j = 1;j <= cnt;j ++)
    for(int k = 1;k <= cnt;k ++)
        if(judge(st[j], st[k]))
            dp[i][j] = (dp[i][j] + dp[i + 1][k]) % mod;
    for(int i = k + 1;i <= n;i ++)
    for(int j = 1;j <= cnt;j ++)
    for(int k = 1;k <= cnt;k ++)
        if(judge(st[j], st[k]))
            dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
    ll ans1 = 0, ans2 = 0;
    // ans1为第k行上方的方案数，ans2是第k行下方的方案数目
    for(int i = 1;i <= cnt;i ++)
        ans1 = (ans1 + dp[1][i]) % mod;
    for(int i = 1;i <= cnt;i ++)
        ans2 = (ans2 + dp[n][i]) % mod;
    if(k == 1)
        printf("%lld\n", ans2);
    else if(k == n)
        printf("%lld\n", ans1);
    else
        printf("%lld\n", ans1 * ans2 % mod);
    return 0;
}