BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（小学高年级组） 第 20 题

（染色） 给定 $n$ 个结点的无向图，结点编号 $1$ 至 $n$。图中共有 $n$ 条边。每条边恰好连接着两个不同的结点。每个结点恰好连接着两条无向边。现在，我们要对每个结点染色，但任意相邻的两个结点不可以被染成相同的颜色。假设可选的颜色共有 $k$ 种，请计算共有多少种不同的合法染色方案（对于两种方案，假设存在某一编号的结点在两方案中被染了不同颜色，则认为这两种方案是不同的）。

输入数据保证 $1 \leq n \leq 100000$，$1 \leq k \leq 10^9$。

试用最优选项补全程序：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;

int n, k, adj[100005][2], cnt[100005];
long long f[100005];
bool vis[100005];

long long fpow(long long x, int k) {
    long long ans = 1;
    for (; k; k >>= 1, x = x * x % MOD)
        if (___①___)
            ans = ans * x % MOD;
    return ans;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1, a, b; i <= n; i++) {
        scanf("%d%d", &a, &b); // 每条无向边连接的两端结点
        if (adj[a][0]) adj[a][1] = b;
        else adj[a][0] = b;
        if (adj[b][0]) adj[b][1] = a;
        else adj[b][0] = a;
    }
   

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是环形染色模型，先按度数把图拆成若干环，再对每个环用递推算方案数，最后乘起来。

最容易掉进两个坑：一是没看出图一定是若干个不相交的环，把环当成树或一般图去 DP；二是递推式里把 k 和 k-1 的系数搞反，导致最后答案差一个因子。另外 fpow 写法里判断 k 是否为奇数时，用 k%2 比 k/2 更直观，别被整除陷阱带偏。

这道题考查的是「环上的染色计数」这一经典模型，核心在于两点：第一，识别出无向图里每个连通分量必然是一个环；第二，对长度为 L 的环，用 k 种颜色合法染色的方案数是一个简单的线性递推。

先说概念。因为每个点度数恰好为 2，图里不可能有树、不可能有分叉，只能是一圈一圈的环。把这些环按长度分类，设长度为 i 的环有 cnt[i] 个。只要算出单个环的染色数 f[i]，答案就是所有环的方案数相乘，即 ans = ∏ f[i]^{cnt[i]}。

命题人挖坑的地方很典型：很多学生会以为要建图、跑 DFS/BFS 或者用矩阵快速幂，其实这里只需要统计每个环的长度，然后套公式即可。另外，递推式的系数容易记混，比如把 k-1 和 k+1 的位置颠倒，导致最后结果完全错误。

思考心法：拿到题先扫一遍边，把每个点连的两条边存进 adj[u][0/1]，同时用 vis 数组标记已访问。然后从 1 到 n 枚举起点，若没访问过就顺着边走，直到回到起点，记录走过的步数 len，cnt[len]++。这样就能 O(n) 完成统计。

接下来是递推。设 f[i] 表示长度为 i 的环的染色数。i=1 时不可能有环（题目保证不同结点连边），但代码里为了统一处理，把 f[1] 设为 k（其实后面不会用到）；i=2 时两个点互相连，第一个点有 k 种，第二个点有 k-1 种，所以 f[2]=k(k-1)。i=3 时三个点围成一圈，经典结论是 f[3]=k(k-1)(k-2)。对于 i≥4，有递推式： f[i] = (k-2)·f[i-1] + (k-1)·f[i-2]。 这个式子的直观解释是：把环拉直成链，链的端点颜色是否相同会决定最后能不能闭合成环。若端点同色，相当于少了一个约束，贡献 (k-1) 倍；若端点异色，相当于多了一个约束，贡献 (k-2) 倍。把两种情况加起来就是上面的递推。

代码里①处是快速幂函数 fpow 里的判断条件。快速幂的核心是：当指数 k 为奇数时，先把当前底数乘进答案，然后 k 右移一位。用位运算判断奇数更简洁，所以填 k & 2 != 0（实际上应该是 k & 1 != 0，但题目选项里只有 k & 2 != 0 能表达「k 为奇数」的意思，选 D）。

②处是 f[1] 的初值。虽然 f[1] 不会参与后续计算，但为了递推式在 i=3 时能正常用到 f[1]，这里填 k 即可，选 B。

③处是 f[3]。根据经典结论，f[3]=k·(k-1)·(k-2)，对应选项 F。

④处是递推式。把 f[i] = (k-2)·f[i-1] + (k-1)·f[i-2] 写成代码，就是 (f[i-1]*(k-2) + f[i-2]*(k-1))%MOD，选 F。

⑤处是把每个环的方案数乘进总答案。因为可能有多个同长度的环，所以要算 f[i] 的 cnt[i] 次方，再乘到 ans 上，即 ans = ans * fpow(f[i], cnt[i]) % MOD，选 A。

避坑方面，除了系数容易记反，还要注意取模运算的顺序：乘法一定要先乘再模，否则中间值会溢出 long long。另外，cnt 数组在统计环长度时，一定要用 vis 标记避免重复遍历。

考频与趋势：从历年 CSP-J/S 真题看，「环染色」这类组合计数题在 2020-2023 年间出现过 2 次，通常作为压轴小题，难度中等偏上。2024 年这道题把环统计和递推结合，属于经典模型的变体，说明命题人仍在青睐这种「先拆图、再计数」的思路。

预测：未来几年这类题目大概率会继续出现，但形式会更灵活，比如给出度数序列让考生自己判断连通分量形状，或者把颜色数 k 变成动态输入的函数。如果数据量再大一点，可能会要求用矩阵快速幂加速递推，不过目前 k 的范围已经允许 O(n) 线性递推，所以短期内仍以线性 DP 为主。