涂抹果酱

https://loj.ac/problem/10172

题目描述

  有一块(N imes M)的矩形蛋糕，每一区域可以染一种颜色，共三种颜色，当前第(K)已涂好，求满足相邻的矩形颜色不相同的方案数。

思路

  显然如果给定的第(K)行不满足要求，我们就不可能存在满足条件的方案，接下来考虑第(K)行满足条件，由于第(K)行一直，所以我们显然可以先倒叙(K-1sim 1)求一次方案数，再正序(K+1sim N)求出一次方案数，把两次的方案数乘起来即可。由于这里有三种颜色可选，所以我们将平常的二进制改为三进制即可。为了避免过多重复操作，我们可以记录(x)和(y)能否共存。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e6;

int p[300],cnt,m;
int f[10010][300];
bool c[300][300];
void dfs(int pos,int last,int s)
{
	if(pos==0)
	{
		p[++cnt]=s;
		return ;
	}
	for(int i=0;i<3;i++)
		if(i!=last)dfs(pos-1,i,s*3+i);
}
bool check(int x,int y)
{
	if(c[x][y]||c[y][x])return 0;
	int a=p[x],b=p[y];
	for(int i=1;i<=m;i++)
	{
		if(a%3==b%3){c[x][y]=c[y][x]=1;break ;}
		a/=3;b/=3;
	}
	if(c[x][y])return 0;
	else return 1;
}
int main()
{
	int n,k;
	scanf("%d%d%d",&n,&m,&k);
	dfs(m,-1,0);
	int s=0,pos=0;
	for(int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		s=s*3+(x-1);
	}
	for(int i=1;i<=cnt;i++)
		if(p[i]==s)pos=i;
//	cout<<endl;
//	for(int i=1;i<=cnt;i++)
//		cout<<i<<' '<<p[i]<<endl;
//	cout<<pos<<endl;
	if(k!=1)for(int i=1;i<=cnt;i++)f[1][i]=1;
	else f[1][pos]=1;
	for(int i=1;i<=n;i++)
	{
		if(i==k)
		{
			for(int j=1;j<=cnt;j++)
				if(check(pos,j))f[i][pos]=(f[i][pos]+f[i-1][j])%mod;
			continue ;
		}
		for(int j=1;j<=cnt;j++)
			for(int k=1;k<=cnt;k++)
				if(check(j,k))f[i][j]=(f[i][j]+f[i-1][k])%mod;
	}
	int ans=0;
	for(int j=1;j<=cnt;j++)
		ans=(ans+f[n][j])%mod;
	if(pos!=0)printf("%d",ans);
	else printf("0");
}