题意
题目描述
Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个n*m 的矩形，它被划分成 n*m个边长为 1的小正方形区域（可以把蛋糕当成n行m列的矩阵）。蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！所以，Sam 要在蛋糕的上表面涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱，三种果酱的编号分别为1,2,3 。为了保证蛋糕的视觉效果，Admin 下达了死命令：相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前，已经涂好了蛋糕第 k行的果酱，且无法修改。
现在 Sam 想知道：能令 Admin 满意的涂果酱方案有多少种。请输出方案数 。若不存在满足条件的方案，请输出0 。输入格式
输入共三行。
第一行：n,m,k；
第二行：k；
第三行：m个整数，表示第k行的方案。
字母的详细含义见题目描述，其他参见样例。输出格式
输出仅一行，为可行的方案总数。
样例
样例输入
2 2 1 2 3样例输出
3数据范围与提示
对于 30% 的数据，。
对于 60% 的数据，。
对于 100% 的数据，。(懒得打了，见代码)
分析
本题是三进制状压，涉及的细节不少，易错点代码中已经用注释标注出来了
注意事项：
- 10进制转3进制的写法（其实很简单）
- 预处理，把三进制转换成编号，对于普通2进制状压是一种优化，本题是必须
- 注意把1，2，3转换成0，1，2，同时要时刻记得本题的0和之前的状压不一样，不代表空位，也是一种颜色
- 注意k==1和k!=1的分类讨论
- 注意第k行矛盾的特判
- 注意初始化（我一开始写错了）
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,M = 244,mod = 1e6;
int n,m;
ll dp[10005][M];//3^5,三进制
int k,a[6];
bool jud[M][M],bo[M];
int num[M],cnt,tmp[M],three[M][6];
void pre()//处理出单行合法的数字
{
int up=pow(3,m);
for(int i=0;i<up;i++)
{
int len=0,t=i;
memset(tmp,0,sizeof(tmp));
while(t)
{
tmp[++len]=t%3;
t/=3;
}
bool flag=0;
for(int j=2;j<=m;j++)//注意j<=m
if(tmp[j]==tmp[j-1])
{
flag=1;
bo[i]=1;
break;
}
if(!flag)
{
num[i]=++cnt;
for(int j=1;j<=m;j++)//注意j<=m,就可以自动补前导零
three[cnt][j]=tmp[j];
}
}
}
void pre2()//处理出jud数组，即两行间合法的情况
{
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int p=1;p<=m;p++)//枚举每一位
{
if(three[i][p]==three[j][p])
{
jud[i][j]=1;//不合法
break;
}
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int sum=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]),a[i]--;//三进制
sum+=pow(3,i-1)*a[i];
//printf("sum=%d
",sum);
}
pre();pre2();
//for(int i=0;i<pow(3,m);i++)
// printf("num[%d]=%d
",i,num[i]);
if(bo[sum])//特判，如果第k行本身矛盾
{
printf("0
");
return 0;
}
if(k==1)
{
dp[1][num[sum]]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int p=1;p<=cnt;p++)
{
if(jud[j][p]) continue;
dp[i][j]+=dp[i-1][p];
dp[i][j]%=mod;
//printf("dp[i][%d]=%lld
",j,dp[i][j]);
}
}
else
{
for(int i=1;i<=cnt;i++)
dp[1][i]=1;
for(int i=2;i<=n;i++)
{
if(i==k)//仔细想想，发现只需要这一个判断
{
for(int p=1;p<=cnt;p++)
if(!jud[num[sum]][p])
dp[i][num[sum]]+=dp[i-1][p],dp[i][num[sum]]%=mod;
}
else
for(int j=1;j<=cnt;j++)
{
for(int p=1;p<=cnt;p++)
{
if(jud[j][p]) continue;
dp[i][j]+=dp[i-1][p];
dp[i][j]%=mod;
}
}
}
}
int ans=0;
for(int i=1;i<=cnt;i++)
{
ans=(ans+dp[n][i])%mod;
//printf("dp[n][%d]=%lld
",i,dp[n][i]);
}
printf("%d",ans);
return 0;
}