涂抹果酱

【题目描述】

Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M 的 矩形，它被划分成 N×M 个边长为 1×1 的小正方形区域（可以把蛋糕当成 N 行 M 列的 矩阵）。蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！所以，Sam 要在蛋糕的上表面涂抹 果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱，三种果酱的编号分别为 1,2,3。为了 保证蛋糕的视觉效果，Admin 下达了死命令：相邻的区域严禁使用同种果酱。但 Sam 在接 到这条命令之前，已经涂好了蛋糕第 K 行的果酱，且无法修改。

现在 Sam 想知道：能令 Admin 满意的涂果酱方案有 多少种。请输出方案数 mod 106。

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

【输入】

输入共三行。

第一行：N,M；

第二行：K；

第三行：M 个整数，表示第 K 行的方案。

字母的详细含义见题目描述，其他参见样例。

【输出】

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

【输入输出样例】

输入

2 2

1

2 3

输出

3

【样例说明】

方案一 方案二 方案三

2 3 2 3 2 3 1 2 3 1 3 2

【数据范围】

对于 30% 的数据，1≤N×M≤20；

对于 60% 的数据，1≤N≤1000,1≤M≤3；

对于 100% 的数据，1≤N≤10000,1≤M≤5。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int maxn=1e4+10;
const int inf=1e6;
int n,m,k,ans,f,dp[maxn][500],ok[3000],c[3000];
int p[]= {1,3,9,27,81,243,729,729*3};

inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline bool chk(int x) {
	int tmp=-1;
	for(int i=1; i<=m; i++) {
		if(tmp==x%3)return 0;
		tmp=x%3,x/=3;
	}
	return 1;
}

inline bool checkk(int x,int y) {
	for(int i=1; i<=m; ++i) {
		if(x%3==y%3) return 0;
		x/=3,y/=3;
	}
	return true;
}

signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read(),m=read(),k=read();
	for(int i=1; i<=m; ++i) {
		c[i]=read();
//		if(c[i]==3) f*=3;
		f=f*3+c[i]-1;
	}
	int num=0;//num1=0;
	for(int i=0; i<p[m]; ++i) {
		if(chk(i)) ok[++num]=i;
//		if(checkk(i,i*3)&&checkk(i,i/3)) kk[++num1]=i;
	}
//	for(int i=1;i<=num;++i)
//		cout<<ok[i]<<' '<<kk[i]<<endl;
//	for(int i=1;i<=p[m];++i) {
//		puts("");
//		for(int j=1;j<=p[m];++j)
//			cout<<checkk(i,j)<<' ';
//	}
	if(k!=1)
		for(int i=1; i<=num; ++i)
			dp[1][ok[i]]=1;
	for(int i=1; i<=n; ++i) {
//		if(i==1) continue;
		if(i==k) {
			if(k==1)
				dp[k][f]=1;
			else
				for(int j=1; j<=num; ++j) {
					int s1=ok[j];
					if(checkk(f,s1))
						dp[k][f]=(dp[k][f]+dp[k-1][s1])%inf;
				}
		}
		else for(int j=1; j<=num; ++j) {
			int s=ok[j];
			for(int h=1; h<=num; ++h) {
				if(checkk(ok[h],s))
					dp[i][j]=(dp[i][j]+dp[i-1][ok[h]])%inf;
			}
		}
	}
	for(int i=1; i<=num; ++i)
		ans=(ans+dp[n][ok[i]])%inf;
	write(ans);
	return 0;
}