题解：P4019 多边形染色

druzewang · 2025-08-24 19:46:23 · 题解

题目传送门

本蒟蒻的第一篇蓝题题解

题意

有一个长度为 n 的环，每个节点可以染上 c 种颜色，且相邻的两个点颜色不能相同，问有多少种染色方式，答案对 987654321 取模。

思路

对于这道题，设置 f_{i,j} 对于前 i 个节点，第 i 个节点染上第 j 个节点的方案数，那么可以得出

主要是看到 c 这么小，状态转移方程里面就肯定是两项。

但是很聪明贱的 Flokirie 又制定了几项规则。

那么先思考有哪些问题：

• 先看环对于 dp 的影响：因为相邻节点颜色必须不相同，所以先枚举第一个节点的颜色，并且最后一个节点单独算就行了。
• 某个节点必选选或者不选那个颜色：只需要定义一个 cant_{i,j} 来记录第 i 个节点能否用颜色 j 即可。
• 让某个节点必须和另外一个相邻的节点颜色相同：只需在定义一个 bang[i] 来记录第 i 个节点是否与第 i - 1 个节点颜色相同即可。

通过上面一系列骚操作，每次找好第 1 个节点的颜色，再去看 2 至 n - 1 这一块节点的 f 值，最后单独计算 f_{n,i} 的值，最后的答案就是

圆满结束！

最后奉上高清无码的代码：

Coding

#include<bits/stdc++.h> 
using namespace std;
#define int long long
const int mod = 987654321; 
int n,m,c;
bool cant[500005][15], bang[500005];
int f[500005][15],ans;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> c;
    for (int i = 1;i <= m;i++) {
        int op,x,y;cin >> op >> x >> y;
        if (op == 1) {
            for (int j = 1; j <= c; ++j) if (j != y) cant[x][j] = false;
        } else if (op == 2) {
            cant[x][y] = true;
        } else {
            bang[max(x,y)] = true;
        }
    }
    for (int color = 1;color <= c;color++) {
        if (cant[1][color]) continue;
        memset(f, 0, sizeof(f));
        f[1][color] = 1;
        for (int i = 2;i < n;i++) {
            for (int j = 1;j <= c;j++) {
                if (!cant[i][j]){
                    if (bang[i]) {
                        f[i][j] = (f[i][j] + f[i-1][j]) % mod; 
                    } else 
                        for (int k=  1;k <= c;k++)
                            if (j != k) f[i][j] = (f[i][j] + f[i-1][k]) % mod;
                }
            }
        }
        for (int i = 1;i <= c;i++) {
            if (!cant[n][i] && i != color){
                if (bang[n]) f[n][i] = (f[n][i] + f[n-1][i]) % mod;
                else
                    for (int j = 1;j <= c;j++)
                        if (i != j) f[n][i] = (f[n][i] + f[n-1][j]) % mod;
            }
        }
        for (int i = 1;i <= c;i++) ans = (ans + f[n][i]) % mod;
    }
    cout << ans;
    return 0;
}

收工！原来 dp 不需要用 Latex 吗。