专栏文章

题解：P4019 多边形染色

ddruzewang
P4019题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5pd3d
此快照首次捕获于
2025/12/02 13:47
3 个月前
此快照最后确认于
2025/12/02 13:47
3 个月前
查看原文

题目传送门

本蒟蒻的第一篇蓝题题解

题意

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

思路

对于这道题，设置 fi,jf_{i,j} 对于前 ii 个节点，第 ii 个节点染上第 jj 个节点的方案数，那么可以得出
fi,j=∑k=1cfi−1,k(k≠j)f_{i,j} = \sum_{k = 1}^{c}f_{i-1,k}(k\ne j)
主要是看到 cc 这么小，状态转移方程里面就肯定是两项。
但是很聪明贱的 Flokirie 又制定了几项规则。
那么先思考有哪些问题：
  • 先看环对于 dp 的影响：因为相邻节点颜色必须不相同，所以先枚举第一个节点的颜色，并且最后一个节点单独算就行了。
  • 某个节点必选选或者不选那个颜色：只需要定义一个 canti,jcant_{i,j} 来记录第 ii 个节点能否用颜色 jj 即可。
  • 让某个节点必须和另外一个相邻的节点颜色相同：只需在定义一个 bang[i]bang[i] 来记录第 ii 个节点是否与第 i−1i - 1 个节点颜色相同即可。
通过上面一系列骚操作，每次找好第 11 个节点的颜色，再去看 22 至 n−1n - 1 这一块节点的 ff 值，最后单独计算 fn,if_{n,i} 的值，最后的答案就是
∑i=1cfn,i\sum_{i=1}^{c}f_{n,i}
圆满结束！
最后奉上高清无码的代码：

Coding

CPP
#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 吗。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...