class="markdown_views prism-atelier-sulphurpool-light">

*C.Squared Graph

处理出原图$G$的所有连通分量，转换后的图相当于所有连通分量两两之间合并，假设当前合并的两个连通分量分别为$A,B$(注意$A,B$可能不同)，合并后得到$C$： 合并规则：
$C$中$(a,b)$和$(a',b')$连通当且仅当存在一个正整数$l$，使得在$A$中$a o a'$,在$B$中$b o b'$都有一条长度为$l$的路径。 分类讨论如下：

• 若$|A|=1$，$C$的连通块数量$=|B|$；$|B|=1$时同理，$C$的连通块数量$=|A|$。
• 否则发现可以通过在一条边上反复横跳，可以走出无限种长度的路径，但是不能改变的路径长度的奇偶性。
  所以若$A,B$都是二分图，转换后有2个连通块，否则只有一个。

$dfs$染 {MOD}一遍，设有$a$个单点，$b$个点数$>1$的二分图，$c$个非二分图。 $ans=a^2+2a(n-a)+2b^2+2bc+c^2$

---

D.Half Reflector

手玩找规律：

• 如果第一个是$A$，改成$B$即可
• 否则将序列左移一位并取反，最后一位改成$A$

可以发现$2n$次以后序列只会有下面两种情况：

• $ABABAB...$，$BBABAB. .$轮换
• $BABABA...$保持不变

情况只取决于序列长度的奇偶。
所以$Kleq 2n$暴力双端队列打标记模拟，否则直接输出答案。

---

*E.Increasing Numbers

任何一个上升数，都可以写成$9$个全1数的和(全1数包括0) 假设用了$k$个上升数，也就是说安排了$9k$个$a_i$使得$sumlimits_{i=1}^{9k} frac{10^{a_i}-1}{9}=n$，即$sumlimits_{i=1}^{9k} 10^{a_i}=9n+9k$ 等价于$9n+9k$的数位和$leq 9k$ 答案最坏是$O(len(n))$级别的。暴力模拟即可。

---

*F.Train Service Planning

这题从昨天下午想到现在，摔 传送门 自己理解的出现的问题： 为什么能把$S(a,n)+S(q,n)$调整成$K$的倍数？ 可以把$S(q,n),S(p,n)$同时加上一个常数$C$使得$S(a,n)+S(q,n)$为$K$的倍数，而所有火车时刻整体后移本质上是等价的。
(也就是说多加了一个$p_0,q_0$的调节变量。。。)
(DZYO神仙代码里$S_i$实际上是$S_{i-1}$，最后调节变量的$S_0$实际上是$q_n+p_n(即S_n)$(因为区间不交的式子只能限制$S_0-S_{n-1}$)) 太神仙了，跪了