[Medium] P12107 [NWRRC2024] Capybara Cozy Carnival
xiezheyuan
·
·
题解
简要题意
给定一个 n 个点的弦图，从点 1 开始，环上点依次为 2,3,\cdots,n。另有 m 条弦，第 i 条弦为 (u_i,v_i)，保证 1\leq u_i<v_i\leq n 且无重边，且两两弦不相交（端点处相交除外）。
求这张图的 k 染色方案数。答案对 998,244,353 取模。
## 思路
感觉这道题挺有趣的。
### 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](https://qoj.ac/submission/986912)。