[LOJ10172]涂抹果酱

题目

题目描述

Tyvj 两周年庆典要到了,Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M的矩形,它被划分成 N×M个边长为 1×1的小正方形区域(可以把蛋糕当成 N 行 M 列的矩阵)。蛋糕很快做好了,但光秃秃的蛋糕肯定不好看!所以,Sam 要在蛋糕的上表面涂抹果酱。果酱有三种,分别是红果酱、绿果酱、蓝果酱,三种果酱的编号分别为 1,2,3。为了保证蛋糕的视觉效果,Admin 下达了死命令:相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前,已经涂好了蛋糕第 K 行的果酱,且无法修改。
现在 Sam 想知道:能令 Admin 满意的涂果酱方案有多少种。请输出方案数 \( mod 10^6\)
若不存在满足条件的方案,请输出 0。

输入格式

输入共三行。
第一行:N,M;
第二行:K;
第三行:M 个整数,表示第 K 行的方案。
字母的详细含义见题目描述,其他参见样例。

输出格式

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

样例

输入样例

输出样例

样例说明

数据范围和提示

对于 30% 的数据,1≤N×M≤20;
对于 60% 的数据,1≤N≤1000,1≤M≤3;
对于 100% 的数据,1≤N≤10000,1≤M≤5。

题解

一开始拿到这道题目发现不就是状态压缩嘛,而且是相邻不重复的计数问题,这种题目早就已经轻车熟路了。
但是仔细看了才发现不简单,不是普通的二进制状压,而是三进制状压。

但是进制本质上都是一样的,我们一边参照二进制状压,一边实现三进制状压。

首先是左移右移,实际上二进制的左移右移就是\(\times 2\)还有/2,既然是三进制,当然是*3还有/3

还有就是实现状态合法判定,具体的在check函数和judge函数的注释里,这两个函数稍微有点不同。

状态转移的话就是上一行的所有合法状态之和(这个和二进制状压是一样的)

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注