题目描述

$Tyvj$两周年庆典要到了,$Sam$想为$Tyvj$做一个大蛋糕。

蛋糕俯视图是一个$N\times M$的矩形,它被划分成$N\times M$个边长为$ 1\times 1$ 的小正方形区域(可以把蛋糕当成$N$行$M$列的矩阵)。

蛋糕很快做好了,但光秃秃的蛋糕肯定不好看!

所以,$Sam$要在蛋糕的上表面涂抹果酱。

果酱有三种,分别是红果酱、绿果酱、蓝果酱,三种果酱的编号分别为$1,2,3$ 。

为了保证蛋糕的视觉效果,$Admin$下达了死命令:相邻的区域严禁使用同种果酱。

但$Sam$在接到这条命令之前,已经涂好了蛋糕第$k$行的果酱,且无法修改。
现在$Sam$想知道:能令$Admin$满意的涂果酱方案有多少种。

请输出方案数$mod\ 10^6$。

若不存在满足条件的方案,请输出$0$ 。

输入格式

输入共三行。
第一行:$N,M$;
第二行:$K$;
第三行: $M$个整数,表示第$K$行的方案。
字母的详细含义见题目描述,其他参见样例。

输出格式

输出仅一行,为可行的方案总数。

样例输入

2 2
1
2 3

样例输出

3

数据范围

对于$100\%$的数据,满足$1\leq N\leq 10000,1\leq M\leq 5$。

菜鸡的咆哮

因为只有有三种果酱,$M$又小得可怜,考虑三进制状压$DP$。

三进制和二进制原理相同,但是用不了位运算了,手动模拟。

注意映射关系!

代码

#include<bits/stdc++.h>
#define maxn 10005
#define mod 1000000
using namespace std;
int n,m,used,kth,posk;
int xx,all; 
int three[100];
int f[maxn][100];
int judge(int num){
    int last=-1;
    for(int i=1;i<=m;i++){//Attention!
        if(last==num%3) return 0;
        last=num%3;
        num/=3;
    }
    return 1;
}
int check(int x,int y){
    for(int i=1;i<=m;i++){//Attention!
        //以上两处不能将x或y除到0就停止,应把m位全部统计完。
        if(x%3==y%3) return 0;
        x/=3;y/=3;
    }
    return 1;
}
int main(){
    cin>>n>>m>>used;
    for(int i=0;i<m;i++){
        cin>>xx; xx--;
        kth+=xx*pow(3,i);
    }
    xx=pow(3,m)-1;
    for(int i=0;i<=xx;i++){
        if(judge(i)) three[++all]=i;
        if(kth==i) posk=all;//把固定行的情况编号单独提出来方便下面dp
    }
    if(!judge(kth)){
        puts("0");
        return 0;
    }
    //注意初始化时的特判
    if(used==1) f[1][posk]=1;
    else for(int i=1;i<=all;i++) f[1][i]=1;
    for(int i=2;i<=n;i++){
        if(i==used){
            for(int k=1;k<=all;k++){
                if(check(kth,three[k])){
                    f[i][posk]+=f[i-1][k];
                    f[i][posk]%=mod;
                }                
            }
        }
        else{
            if(i-1==used){
                for(int j=1;j<=all;j++){
                    if(check(three[j],kth)){
                        f[i][j]+=f[i-1][posk];
                        f[i][j]%=mod;
                    }
                }
            }
            else{
                for(int j=1;j<=all;j++){
                    for(int k=1;k<=all;k++){
                        if(check(three[j],three[k])){
                            f[i][j]+=f[i-1][k];
                            f[i][j]%=mod;
                        }                
                    }
                }        
            }
        }    
    }
    int ans=0;
    for(int i=1;i<=all;i++){
        ans+=f[n][i]; ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}