【LOJ 10172】涂抹果酱

题目描述

Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 $\mathrm{N\times M 的矩形，它被划分成 N\times M 个边长为 1\times 1 的小正方形区域（可以把蛋糕当成 NNN 行 MMM列的矩阵）。蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！所以，Sam\; 要在蛋糕的上表面涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱，三种果酱的编号分别为 1,2,31,2,31,2,3。为了保证蛋糕的视觉效果，Admin\; 下达了死命令：相邻的区域严禁使用同种果酱。但\; Sam\; 在接到这条命令之前，已经涂好了蛋糕第 KKK 行的果酱，且无法修改。现在\; Sam\; 想知道：能令\; Admin\; 满意的涂果酱方案有多少种。请输出方案数 mod106。若不存在满足条件的方案，请输出 000。}$

输入格式

输入共三行。
第一行：N,MN, MN,M；
第二行：KKK；
第三行：MMM 个整数，表示第 KKK 行的方案。
字母的详细含义见题目描述，其他参见样例。

输出格式

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

样例

样例输入

2 2 
1 
2 3

样例输出

3

样例说明

方案一	方案二	方案三
$\text{2 3 1 2}$	$\text{2 3 3 1}$	$\text{2 3 3 2}$

数据范围与提示

对于 30% 的数据，$\mathrm{1\le N\times M\le 20；对于\; 60\%\; 的数据，1\le N\le 1000,1\le M\le 3；对于\; 100\%\; 的数据，1\le N\le 10000,1\le M\le 5。}$

$\mathrm{题解：三进制的状态压缩类DP，刚拿到题目只能弱弱地DFS扫}$

$\mathrm{看了题解之后明白啦！！！加了注释昂}$

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N=10003;
const int mod=1000000;
int KKK,flag,tnt,n,m,k;
int f[N][1505],s[1505];
int cnt,x,ans;
//f[i][j]表示的是第i行状态为s[j]的方案个数 
bool check(int x){
    int tmp=0x3f;
    for(int i=1;i<=m;i++){
        if(tmp==x%3) return false;
        tmp=x%3; x/=3;
    }
    return true;
}

bool judge(int a,int b){
    for(int i=1;i<=m;i++){
        if(a%3 == b%3) return false;
        a/=3; b/=3;
    }
    return true;
}
int main(){
    freopen("涂抹果酱.in","r",stdin);
    freopen("涂抹果酱.out","w",stdout);
    cin>>n>>m>>KKK;
    int fire=pow(3,m);
    for(int i=0;i<fire;i++)
        if(check(i)==1) s[++cnt]=i;
    for(int i=1;i<=m;i++){
        cin>>x;
        tnt=tnt*3+x-1;
    }
    for(int i=1;i<=cnt;i++)
        if(tnt==s[i]) { flag=i; break; }
        
    if(!flag) { puts("0"); return 0; }
    for(int i=1;i<=n;i++){
        if(i==KKK){
            if(i==1) f[i][flag]=1;//第一行特殊处理 
            else{
                for(int j=1;j<=cnt;++j)//枚举上一行状态 
                    if(judge(s[flag],s[j]))
                       f[i][flag]=(f[i][flag]+f[i-1][j])%mod;
            }  
        }
        else{
           for(int j=1;j<=cnt;j++){//枚举上一行的状态 
                if(i==1) f[i][j]=1; //第一行特殊处理 
                else{               
                   for(int k=1;k<=cnt;k++)//枚举这一行状态 
                       if(judge(s[j],s[k]))
                          f[i][j]=(f[i][j]+f[i-1][k])%mod;
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++)
        ans=(ans+f[n][i])%mod;
    cout<<ans<<endl;
    return 0;
}