题解 P2435 【染色】

· · 题解

Update on 2026/05/12: 修改了代码中的错误（感谢 @DaydreamWarrior 与 @REFLAME_ASH 指出），优化了代码，采用了规范的格式。

题意：给你一个 n\times m 的网格，然后给出第一行和最后一行的染色方案，问剩下的方格的染色方案数，使得没有两个相邻的方格颜色相同。对 376544743 取余数。

首先对于 k=2 的情况，显然是好判断的：首先，第一行两个格子的颜色必须不同。然后发现，确定第一行之后，后面的填法如果存在，那么唯一。并且，对于第 i 行的填法，如果 2\mid i，那么它的填法正好是第一行 0/1 翻转；否则它的填法和第一行相同。这样我们就可以轻松判断是否有合法的填法。时间空间复杂度都是 \mathcal O(m)。

对于 k>2 的情况，我们考虑使用轮廓线 \rm dp 来解决这个问题。这是一种特殊的状态压缩 \rm dp。

我们从上到下，从左到右考虑问题。假设当前填到格子 (i,j)，要考虑下一个格子怎么填。我们发现，只需要记录前面的轮廓线的颜色状态 sta 即可。轮廓线就是，最后 m 个格子 (i-1,j),\cdots ,(i-1,m),(i,1),\cdots,(i,j)（如果相应格子存在）的颜色状态。不难发现，只有这些格子和 (i,j) 以后的格子有相邻，会影响到后面的填法。

于是，我们考虑下一个格子 (i^*,j^*) 的颜色 c 要满足哪些要求。发现如下最多两条：

这两个格子的颜色信息都记录在 sta 里面，于是我们在枚举 c 时，很容易判断是否满足要求，并且依此决定是否进行状态转移。

我们只填到第 n-1 行。最后统计答案的时候，判断一下第 n-1 行和第 n 行的颜色填法是否冲突即可。

实现的时候，考虑用 m 位 k 进制数的方式来存储状态。另外，注意到每个格子的转移只与上一个格子的状态相关，于是可以使用滚动数组优化空间。最后，我们只对那些方案数 \neq 0 的格子进行尝试扩展，这样可以至少筛去轮廓线状态本来就不合法的那些状态。由简单的组合数学可知，每个格子的需要扩展状态总数从 k^m 个，被压缩到不超过 k^2(k-1)^{m-2} 个。

时间复杂度 \mathcal O(nmk^m)，空间复杂度 \mathcal O(k^m)。

下面是笔者的 \rm cpp 代码。

::::info[代码]

#include<cstdio>
const int mod=376544743;
int dp[2][300005],b[15],ans,sp1[100005],sp2[100005];
int n,m,kk,now,maxs,s1,s2;
void update(int x1,int x2){dp[now][x2]=(dp[now][x2]+dp[1-now][x1])%mod;}
void put(int x,int y,int lst){if (y/b[m-1]!=x&&(y%kk!=x||lst)) update(y,(y*kk+x)%b[m]);} 
int check(int x,int y,int m)
{
    for (int i=1;i<=m;i++)
    {
        if (x%kk==y%kk) return 0;
        x=x/kk,y=y/kk;
    }
    return 1;
}
int main()
{
    scanf("%d%d%d",&n,&m,&kk);
    if (kk==2)
    {
        int flag=1;
        for (int i=1;i<=m;i++) scanf("%d",&sp1[i]);
        for (int i=1;i<=m;i++) scanf("%d",&sp2[i]);
        for (int i=1;i<=m;++i)
        {
            if ((i>1)&&(sp1[i]==sp1[i-1]||sp2[i]==sp2[i-1])) flag=0;
            if ((sp1[i]+n)%2==sp2[i]) flag=0;
        }
        printf("%d\n",flag);
        return 0;    
    }
    b[0]=1;for (int i=1;i<=m;i++) b[i]=b[i-1]*kk;
    maxs=b[m]-1;
    for (int i=1;i<=m;i++)
    {
        int x,y=-1;
        scanf("%d",&x);
        if (i!=1&&x==y) return puts("0"),0;
        s1=s1*kk+x;y=x;
    }
    for (int i=1;i<=m;i++)
    {
        int x,y=-1;
        scanf("%d",&x);
        if (i!=1&&x==y) return puts("0"),0;
        s2=s2*kk+x;y=x;
    }
    dp[0][s1]=1;
    now=0;
    for (int i=1;i<n;i++)
        for (int j=1;j<=m;j++)
        {
            if (i==1&&j!=m) continue;
            if (i==n-1&&j==m) break;
            int lst=(j==m);
            now=1-now;
            for (int k=0;k<=maxs;k++) dp[now][k]=0;
            for (int k=0;k<=maxs;k++)
                if (dp[1-now][k]) for (int p=0;p<kk;p++) put(p,k,lst);
        }
    for (int i=0;i<=maxs;i++) if (dp[now][i]&&check(i,s2,m)) ans=(ans+dp[now][i])%mod;
    printf("%d\n",ans);
    return 0;
}

::::

消耗时间 \tt 627ms，消耗内存 \tt 1.14MB，代码长度 \tt 1544B。

::::info[一些怀旧故事] 这篇题解本来是由笔者于七年前的一个五月，\rm 2019/05/04 发布的，原文在这里。当时笔者还是一个小学生，对 \sf OI，对计算机科学，对世界，几乎什么也不懂。

在七年后的这个五月，2026/05/12，笔者偶然发现这篇题解成为最高赞题解，但是没有使用 \LaTeX 和正确的 \rm markdown 格式，于是就修改了一下。在阅读原文时，笔者被当时原文的口吻语气逗笑了，真的能感受到一个小朋友（算嘛）经过几天努力通过一个题时欣喜又有点想炫耀，同时又要兼顾卖弱的复杂心情（笑）。在阅读代码，并按照评论区老哥的意见修正错误时，笔者惊奇地发现写的代码里面充满了大量无意义的所谓卡常语句，比如 inline，register之类的，现在已经被弃用的东西；还有把所有的 i++ 都改成了 ++i，但是实际上这些编译器最终都会编译成同样的机器码；还有努力不用拼音，但是最后发现实际上缺乏意义的变量名，等等。笔者现在猜想可能是因为当时笔者一直超时（2019/04/20 一天交了 10 发才通过），盲目采取各种有用没用的可能的优化，并且只会用 \textrm {dev\_cpp} 自带的 \rm gcc~ 4.9.2 编译器，只会用 \textrm {C++98} 的内容的缘故。然而现在，笔者已经换了 \rm gcc~16.1.0 编译器，\textrm {C++26} 标准也即将发布，人工智能也在包括算法竞赛在内的许多领域赶上甚至超过人类。虽然笔者现在对包括计算机科学之内的世界上的大多数事物还是很缺乏了解（现在笔者的主专业也不是学计算机科学的），但是，笔者不得不感叹，自己的视野，客观的世界，变化真大啊。 ::::