自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:12:47，当前版本为作者最后更新于2025-04-20 19:33:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

简要题意

给定一个 $n$ 个点的弦图，从点 $1$ 开始，环上点依次为 $2,3,\cdots,n$。另有 $m$ 条弦，第 $i$ 条弦为 $(u_i,v_i)$，保证 $1\leq u_i<v_i\leq n$ 且无重边，且两两弦不相交（端点处相交除外）。

求这张图的 $k$ 染色方案数。答案对 $998,244,353$ 取模。

$T$ 组数据。$3\leq n\leq 10^9,0\leq \sum m\leq 2\times 10^5,2\leq k\leq 10^6$。

思路

感觉这道题挺有趣的。

Part 1

首先如果 $m=0$ 怎么做？可以先破环成链（钦定切断 $(1,n)$ 边）。那么就转换成了链上的问题：给 $n$ 个点的链 $k$ 染色，使得 $1,n$ 两端点颜色不同的方案数。

对于这个问题，有一个经典 dp：设 $f(i,0/1)$ 考虑到链上点 $i$，该点的颜色与点 $1$ 不同或相同的方案数，转移也是平凡的：

$$\begin{aligned} &f(i,0)=(k-2)f(i-1,0)+(k-1)f(i-1,1)\\ &f(i,1)=f(i-1,0) \end{aligned} $$

边界 $f(1,0)=0,f(1,1)=1$（这里假设点 $1$ 的颜色已经确定，如果没有确定最后的答案要乘以 $k$）。

直接 dp 时间复杂度是 $O(n)$ 难以承受，不过这很容易矩阵优化：

$$\begin{bmatrix}f(i-1,0)& f(i-1,1)\end{bmatrix} \begin{bmatrix} k-2& 1\\ k-1& 0 \end{bmatrix}=\begin{bmatrix}f(i,0)& f(i,1)\end{bmatrix} $$

于是可以借助矩阵快速幂做到 $O(\log n)$。

Part 2

现在加上 $m$ 条弦，弦图上的弦不交，对应到破环成链后的链上，就是区间两两无交或包含（特别地，认为端点重合为无交），不妨先考虑两两无交的情况。

假设 $n=12$，$m=3$ 条弦分别为 $(2,4),(4,6),(9,10)$，那么这 $3$ 条弦实际上将链分成了 $6$ 个部分：$[1,2],[2,4],[4,6],[6,9],[9,10],[10,12]$。注意到这 $6$ 个部分中，只有弦对应的区间 $[2,4],[4,6],[9,10]$ 才有端点颜色不同的限制，其他区间是没有这一限制的，最后还要求两端的颜色不同。

不妨采用增量法统计，记录 $f_0,f_1$ 表示当前的部分中，末尾点与第一个点的颜色不同或相同的方案数。初始时显然也有 $f_0=0,f_1=1$。

现在加入一个新部分，假设这一部分中，首尾点颜色相同的方案数为 $g_1$，首尾点颜色不同的方案数为 $g_0$（求 $g_0,g_1$ 就是 Part 1，显然对于弦对应的区间，需要强制钦定 $g_1=0$）。

那么有转移（两条转移依次进行）：

$$\begin{aligned} &f_1\gets f_0\cdot \frac{g_0}{k-1}+f_1\cdot g_1\\ &f_0\gets (f_0+f_1)\cdot (g_0+g_1)-f_1 \end{aligned} $$

第二条转移就是在计算补集方案，关键在于第一条转移。

假如这一部分的首端点与整条链的第一个端点相同，那么这一部分的首尾点颜色也就相同了，直接乘上方案即可 $f_1\cdot g_1$，否则我们需要强制钦定 $g_0$ 中最后一个点颜色为整条链的第一个端点相同，由于对于这一部分的最后一个点的颜色，每种颜色都是对称的，所以直接除以 $k-1$ 就可以了。

时间复杂度 $O(m\log (n+m))$，其中 $O(m\log m)$ 来自于对所有弦的排序。

Part 3

考虑一般的问题。由于区间两两或无交，或包含。那么根据处理该类问题的经验，很容易将所有区间建树。

这个树和常见的线段树或 BIT 相似。具体地，我们将每个区间看成一个节点，它在树上的深度为包含它的区间数量（这里将 $[1,n]$ 需要考虑的一个区间），若区间 $A$ 包含区间 $B$，则在树上，$A$ 为 $B$ 的祖先。

（由于我不是很会画图，所以就不画图了，大家可以拿笔出来自己试试）

这个树的建法很多，比如按照大小排序，查找这个区间被哪一个区间覆盖之类的（这一步注意细节）。

建出这个树后，我们可以沿用 Part 2 的过程，只需要将 Part 2 中对于一个部分直接调用 Part 1 改为如果这是一条弦对应的区间递归下去就可以了。

时间复杂度不变，仍然为 $O(m\log(n+m))$。

Submission in QOJ。