一道三进制状压的好题。
题目描述:
Tyvj 两周年庆典要到了，Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M的矩形，它被划分成 N×M个边长为 1×1的小正方形区域（可以把蛋糕当成 N 行 M 列的矩阵）。 蛋糕很快做好了，但光秃秃的蛋糕肯定不好看！ 所以，Sam 要在蛋糕的上表面涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱， 三种果酱的编号分别为 1,2,3.为了保证蛋糕的视觉效果，Admin 下达了死命令： 相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前， 已经涂好了蛋糕第 KKK 行的果酱，且无法修改。现在 Sam 想知道：能令 Admin 满意的涂果酱方案有多少种。请输出方案数 mod1e6。若不存在满足条件的方案，请输出 0。
输入格式
输入共三行。
第一行：N,M；第二行：K；第三行：M 个整数，表示第 K 行的方案。字母的详细含义见题目描述，其他参见样例。输出格式
输出仅一行，为可行的方案总数。
样例
样例输入
2 2 1 2 3
样例输出
3
解题思路：
这道题关键在判断合法情况，第k行特判一下即可。
1.判断一个三进制数是否有相同数字相邻的情况，不能模拟二进制左移右移的情况，
因为这里有3个数字，左移右移会出现有0的影响。
2.判断不同行是否有相同数字相邻，模拟二进制的&判断一下即可。
代码：
#include#define ll long long #define R registerusing namespace std;int n,m,k,mod=1e6,a[250],sk,num,top,ans,f[10005][250];inline int ksm(R int x,R int p){ R int tot=1; while(p) { if(p&1) { tot=tot*x; } x=x*x; p>>=1; } return tot;}inline int check(R int x,R int y){ for(R int i=1;i<=m;++i){ if((x%3)==(y%3))return 0; x/=3; y/=3; } return 1;}inline int judge(R int x){ R int y=-1; for(R int i=1;i<=m;++i) { if(y==x%3)return 0; y=x%3; x/=3; } return 1;}inline void init(){ for(R int i=0;i<=242;++i){ R int x=i,tot=0; while(x) { x/=3; ++tot; } if(tot>=m+1)break; if(judge(i)){ a[++num]=i; if(i==sk)top=num; } }}int main(){ scanf("%d%d",&n,&m); scanf("%d",&k); for(R int i=1;i<=m;++i) { R int t; scanf("%d",&t); sk+=(t-1)*ksm(3,i-1); } if(!judge(sk)) { printf("0"); return 0; } init(); if(k==1) f[1][top]=1; else for(R int i=1;i<=num;++i) f[1][i]=1; for(R int i=2;i<=n;++i)//当前第几行 { if(i==k) { for(R int t=1;t<=num;++t) if(check(a[top],a[t])) f[i][top]=(f[i][top]+f[i-1][t])%mod; } else { for(R int j=1;j<=num;++j)//当前行状态 { if(i-1==k) { if(check(a[j],a[top])) f[i][j]=(f[i][j]+f[i-1][top])%mod; } else { for(R int t=1;t<=num;++t)//上一行状态 if(check(a[j],a[t])) f[i][j]=(f[i][j]+f[i-1][t])%mod; } } } } for(R int i=1;i<=num;++i) ans=(ans+f[n][i])%mod; printf("%d",ans%mod); return 0;}
这道题关键在于舍弃不合法情况的判断.