CF2023C C+K+S 题解

前置知识：哈希/KMP

题目链接：洛谷、Codeforces。

有点牛的一道题。

首先，既然两张图所有的环长都是 \(k\) 的倍数，那么考虑做一个比较厉害的处理：对图染色。令 \(u\) 的颜色为 \(c_u\)，如果有边 \(u \rightarrow v\)，那么 \(c_v = (c_u+1) \mod k\)。这样最多有 \(k\) 种颜色，范围是 \([0,k)\)。

然后考虑将两张图合并的过程，显然也要遵循以上的染色规则。那么对于每个出点 \(s\)，都要有一个入点 \(t\) 使得 \(c_t=(c_s+1)\mod k\)。

于是一种可行的方案就是：将第二张图的颜色不停循环位移，如果存在一种方案，使「第一张图染 \(x\) 的颜色的出点数」等于「第二张图染 \((x+1)\mod k\) 的颜色的入点数」（反之亦然），那么说明存在题目所求方案。这个时间复杂度是 \(\mathcal{O}(n^2)\) 的。

观察一下上述过程，发现随着第二张图的颜色的轮换，统计每个颜色出现几次的 \(cnt\) 数组的元素也在轮换。所以只需第二张图的入点 \(cnt\) 数组是第一张图的出点 \(cnt\) 数组的轮换（反之亦然），倍长之后哈希/KMP 判断即可。时间复杂度是 \(\mathcal{O}(n)\)。