电子商务网站规划与管理,装饰设计软件,wordpress博客栏目设计,wordpress 主机屋题目链接 一道三进制状压的好题。 题目描述: Tyvj 两周年庆典要到了#xff0c;Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 NM的矩形#xff0c;它被划分成
NM个边长为 11的小正方形区域#xff08;可以把蛋糕当成 N 行 M 列的矩阵#xff09;。蛋糕很快做好了#x…题目链接 一道三进制状压的好题。 题目描述: 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.判断不同行是否有相同数字相邻模拟二进制的判断一下即可。 代码 #includebits/stdc.h
#define ll long long
#define R register
using namespace std;
int n,m,k,mod1e6,a[250],sk,num,top,ans,f[10005][250];
inline int ksm(R int x,R int p)
{R int tot1;while(p){if(p1){tottot*x;}xx*x;p1;}return tot;
}
inline int check(R int x,R int y)
{for(R int i1;im;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 i1;im;i){ if(yx%3)return 0;yx%3;x/3;}return 1;
}
inline void init()
{for(R int i0;i242;i){R int xi,tot0;while(x){x/3;tot;}if(totm1)break;if(judge(i)){ a[num]i; if(isk)topnum;}}
}
int main(){scanf(%d%d,n,m);scanf(%d,k);for(R int i1;im;i){R int t;scanf(%d,t);sk(t-1)*ksm(3,i-1);}if(!judge(sk)) {printf(0);return 0;}init();if(k1)f[1][top]1;elsefor(R int i1;inum;i)f[1][i]1;for(R int i2;in;i)//当前第几行{if(ik){for(R int t1;tnum;t)if(check(a[top],a[t]))f[i][top](f[i][top]f[i-1][t])%mod;}else{for(R int j1;jnum;j)//当前行状态{if(i-1k){if(check(a[j],a[top]))f[i][j](f[i][j]f[i-1][top])%mod;}else{for(R int t1;tnum;t)//上一行状态if(check(a[j],a[t]))f[i][j](f[i][j]f[i-1][t])%mod;}}}}for(R int i1;inum;i)ans(ansf[n][i])%mod;printf(%d,ans%mod);return 0;
} 这道题关键在于舍弃不合法情况的判断. 转载于:https://www.cnblogs.com/sky-zxz/p/9865604.html
