问题概述

给定一个无向图，使用 $k$ 种颜色给顶点染色，要求有边相连的两个顶点颜色不同。对于多个 $k$ 的取值，分别计算染色方案数。

算法分析

关键观察

1. 色多项式：图的染色方案数是关于颜色数 $k$ 的 $n$ 次多项式 $P(G,k)$
2. 连通分量独立性：整个图的染色方案数是各连通分量的染色方案数之积
3. 多项式性质：知道 $n+1$ 个点值就能唯一确定 $n$ 次多项式

核心思路

阶段一：预处理

1. 连通分量分解：使用 DFS 或并查集将图分解为连通分量
2. 分量处理：对每个连通分量单独计算色多项式

阶段二：计算色多项式

方法选择取决于分量大小：

1. 小分量 ($n \leq 15$)：状压DP

• 状态：$dp[mask][c]$ 表示已染色点集 $mask$，使用了 $c$ 种颜色的方案数
• 转移：枚举下一个要染色的点和可用的颜色
• 复杂度：$O(2^n \cdot n^2)$

2. 边数较少 ($m \leq 24$)：容斥原理

• 使用包含排斥原理计算：$$P(G,k) = \sum_{S \subseteq E} (-1)^{|S|} k^{c(S)}$$ 其中 $c(S)$ 是保留边集 $S$ 时的连通分量数
• 复杂度：$O(2^m)$

3. 特殊图结构

• 环图：$P(C_n,k) = (k-1)^n + (-1)^n(k-1)$
• 树图：$P(T_n,k) = k(k-1)^{n-1}$
• 二分图：可用简单公式计算

阶段三：多项式插值

对于每个连通分量：

1. 计算 $n+1$ 个点值：$P(0), P(1), \ldots, P(n)$
2. 使用拉格朗日插值构建多项式
3. 将所有连通分量的多项式相乘，得到整个图的色多项式

阶段四：回答查询

对于每个 $k_i$，直接在色多项式中代入求值：

• 由于 $k_i$ 可能很大 ($\leq 10^9$)，需要 $O(n)$ 多项式求值
• 结果对 $10^9+7$ 取模

复杂度分析

• 预处理：$O(n + m)$ 的连通分量分解
• 多项式计算：取决于最大连通分量大小
  • 状压DP：$O(2^{n_{\max}} \cdot n_{\max}^2)$
  • 容斥：$O(2^{m_{\max}})$
• 插值：$O(n^2)$ 总体
• 查询：$O(z \cdot n)$

实现细节

1. 模运算：使用 $10^9+7$ 模数
2. 组合数预处理：预计算阶乘和逆元
3. 多项式运算：实现多项式乘法和插值
4. 优化：对于相同大小的连通分量，可以复用计算结果

针对子任务的特殊处理

• Subtask 1：直接暴力染色或小范围DP
• Subtask 2：状压DP是主要方法
• Subtask 3：容斥原理更优
• Subtask 4：利用环图的特殊公式

这种分层处理方法能够高效处理大规模数据，同时保证小范围情况的正确性。