常州集训做题记录总集

alexbear103 · 2025-06-05 14:15:34 · 个人记录

题单里的题还没做完。只写了做完的

5.24 信友队模拟赛

T1

邪道就不介绍了

首先有一个题意转化。设 f(x) 为 \min \sum a_i 满足 \sum a_i! = x。然后我们要求的就是\min\limits_{f(x) > n} x

考虑我们既然要让 \sum a_i 最小，那我们一个数 k 肯定不会使用超过 k 次，不然我们直接用 (k + 1)! 就可以替换它。

然后就会发现，这是一个类似进制的东西。因为\sum\limits_{i = 1}^k i \times i! = \sum\limits_{i = 1}^k (i + 1)! - i! = (k + 1)! - 1，所以每个数都有且仅有一个表示方法。设这个表示方法为 x = \sum\limits_{i = 1}^p b_i \times i!，那么这个表示方法的代价（即\sum a_i）为\sum\limits_{i=1}^p i\times b_i

又有 f(x + 1) \le f(x) + 1（我们直接添加一个 1! 一定是合法的），所以第一个越界的一定取到 n + 1，即我们只需要求 \min \limits_{f(x) = n + 1} x。

我们从高位往低位贪心地填。取b_i = \min b_i 满足 \sum\limits_{j = i}^p j\times b_j + \sum \limits_{j = 1} ^ {i - 1} j^2，即考虑把低位填满的情况下当前位最少要填多少，即可获得单次 O(n^{\frac 1 3}) 的做法。

然后我们考虑直接把这个数构造出来。

考虑p = \max p 满足 \sum\limits_{i = 1}^p i^2 \le n，先考虑把这些位填满。考虑取 b_{p+1} = \lfloor \frac {n + 1 - \sum\limits_{i = 1}^p i^2}{p + 1} \rfloor + 1，此时一定能保证代价会超出n + 1。超过了 r = b_{p + 1} (p + 1) + \sum\limits_{i = 1}^p i^2 - n - 1。考虑超出的代价减掉。为了使最后的值最小，我们肯定要减掉一个最高的位。那考虑直接减去 r! 即可。

最后的答案可以表示为 (b_{p + 1} + 1)(p+1)! - 1 - r!。其中 (b_{p + 1} + 1)(p+1)! 表示了第 p + 1 位填 b_{p+1}，低位填满时的数值。

T2

遇到绝对值一定要考虑调整结果全部是原数

则路径是若干h相同的连续段组成的。考虑用其中h不变的那个点来刻画。即设p_1,p_2,...,p_k，表示第一个连续段全部改成h_{p_1}，第二个全部改成h_{p_2}，……

然后一个比较重要的思想就是，由于p是连续段中间的一个点，相关状态不好处理；我们考虑用p是起点的状态拼出来。即设f_{p,v}为从p出发走到v并且全都改成h_p的最小花费。这个可以dij跑出来。

然后考虑一个连续段的端点是不确定的，也不好做；此时考虑在关键点间转移。记 c_{p,q} = \min\limits_k f_{p,k} + f_{q,k} + C \times |h_p - h_q| - d_k * |h_k - h_q|，表示将 p...k 改成 h_p，并将 nxt_k...q 改成 h_q 的最小代价。然后可以dij计算路径 p_1.\rightarrow p_k 的最小代价 dis_{p_1,p_k}。

然后我们考虑 s\rightarrow p_1\rightarrow p_k\rightarrow t 的代价可以用三个部分拼起来：f_{p_1, s} + dis_{p_1,p_k} + f_{p_k,t}。考虑 f_{p_1,s} 与 f_{p_k,t} 无关，可以分开枚举，可以做到 O(n^3)。

5.28 信友队模拟赛

T1

要培养快速切出贪心结论题的能力啊啊。

假如后缀和为负，就必须填左括号。否则考虑填右括号。这样只要终点不是右括号就能构造出一组合法的解。

现在考虑这为什么是最小的：我们会把左括号尽量放在右边。即有机会填左括号的时候我们就会优先填。然后因为前缀和是严格单增的所以左括号越靠右越好。

T3

奇妙。首先你需要读题。更首先是你需要在切完T1还有充足的时间读题。总之多打CF

先考虑树的情况。贪心策略是：第一次从某个 t_p = 1 的点 p 出发，走一条到叶子最长的路径。之后相当于可以选择1-邻域中的点作为起点。

于是我们考虑一个子树中的最长链可以被经过几次。先按照最长链把树进行剖分。那一条链可以被经过的次数就是前驱链中的 \sum t

转移：考虑一条链上只有链顶可以计算前驱链的贡献，其它位置并不能被重复经过，于是我们需要单独记一个tag表示前驱链部分的贡献。在跳到不同链的时候计算一下。

然后考虑DAG的情况，这样的计算方法并不会出锅。（你走非树边点的序列一定是不一样的。

那我们只需要拓扑排序然后处理一下这个东西就好了

6.1 信友队模拟赛

T1

好似（！

树上问题能用的工具应该不多。lca，二维偏序，直径。能贴上的都想想。

第一步观察比较明显。就是你不能走回头路。然后手玩样例发现，如果你对着走占优势就直接对着走，否则尝试找一条逃げ道。具体来说，对于 (x,y,k)，x 的这条路径要求长度至少为 \lceil \frac k 2 \rceil 且与 y 的距离不小于 \lfloor \frac k 2 \rfloor。

然后你需要想到直径。发现这个问题就是，你需要ban掉一个子树或者一个子树的补集，然后求当前的直径（最长链端点一定是直径端点。）

这件事情可以用线段树实现。先把树拍平，然后 O(\log n) 合并直径pushup即可。

细节就是，倍增LCA的log是满的。建议换成剖以减少常数。

网络流

CF2046D For the Emperor!

支持拆三个点建图谢谢喵。

先缩点。

一个SCC一定要有带有计划的信使停驻过。可以直接向土著信使派发计划，或者选择让其他信使经过。

将一个点拆为三个：in,out,rest。最初认为代价是n\cdot \inf

对于原图上的边(u,v)，连一条(u,d) \rightarrow (v,d+1)，容量为\inf；连一条(u,d) \rightarrow (v,d)，容量为1。则割掉后者意味着强制让距离+1，即将边权修改为1

故若(p,d)和S相连则说明p点距离可以被d控制住。如果希望dis_n > d_0，则需要使(n,0) 到 (n,d_0) 全部被割到 T 集合中。故考虑将它们全部与 T 相连，然后计算最小割是否\le k

可能需要考虑的就是两个链之间的边是否会被割两次。可以证明，只有最下面一条边是有价值的。设我们要割掉(u,d) \rightarrow (v,d)，那么只要走 (u,d) \rightarrow (v,d+1) 就可以到达所有 (v,d+1) 及以上的点。割掉 (u,d) \rightarrow (v,d) 上方的边无法改变这一点，故不如不割。

ARC142E Pairing Wizards

广义切糕模型说是。

首先考虑转化题意。对于 (x,y)，显然不劣的对应方式是大的对大的，小的对小的。

即我们需要做到 \min(a_x, a_y) \ge \min(b_x, b_y) 且 \max(a_x, a_y) \ge \max(b_x, b_y)

两个限制还带\min \max不是很好处理。考虑先将所有 a_x,a_y 调到 \min(b_x,b_y)。此时只需要 a_x \ge \max(b_x,b_y) 或 a_y \ge \max(b_x,b_y)。

然后我们发现切糕模型两个不等号得是反向的。然后我们考虑人类智慧：将a中的元素分为 a_x \ge b_x 和 a_x < b_x 两组。

如果a_x,a_y都在第一组就不用讨论了。且不可能都在第二组。我们考虑第二组建反链，不等号也就随着反过来了。

连边的时候需要注意一下边界条件。考虑两个位置都取边界值的时候是割的是哪两条边即可。

CF1427G One Billion Shades of Grey

切糕（片）模型说是（x

还是比较难证

[AGC031E] Snuke the Phantom Thief

奇妙邪道。正攻是有源汇上下界费用流（）

考虑枚举将要选的个数p，将前缀a_i最多选b_i个转化为坐标第b_i + 1大的点坐标 > a_i；将后缀a_i最多选b_i个转化为坐标第p - b_i大的点坐标< a_i

记横纵坐标第i名的坐标区间分别为X_i 和 Y_i

考虑 x_k 若在 X_i 中则连 X_i \rightarrow k, y_k 若在 Y_j 中则连 k \rightarrow Y_j

连S\rightarrow X,Y\rightarrow T，将k点点权设为v_k，跑费用流。须满流才能更新答案。

连通性问题

还是先写点讲课的内容。

[AGC071C] Orientable as Desired

思路就是，由特殊情况到一般情况。

先考虑赋值 \forall x_i = 0，这种情况要求原图是二分图。因为所有点要不全定成出边要不全定成入边，然后取相反的度。如果不是二分图就寄了。

然后考虑选定一个点 p 令 x_p = k，其余 x_i = 0。那么为了保证剩下的都是0，我们只能整体翻转某个vDCC中的边的方向。记 p 在相邻的vDCC的 i 中有 c_i 个邻居。那么若可以做到 x_p = k，必须能用所有的 c_i 拼出 k。

又因为 k \le \sum c_i。这件事情等价于对所有 c_i 排序后 \forall i，c_i \le sum_{i - 1} + 1。证明的话，必须满足这个才能使DP数组平移取并后连续。

现在可以得出一个必要条件：图是二分图且对于所有点 p 满足上述的 \forall i，c_i \le sum_{i - 1} + 1

现在考虑充分性

首先考虑一个树的情况。发现树是任意的 \{x_i\} 都有解。先从根开始定向。解决到子树时会发现只有到父亲的边已经被定向，那我们只需要选出 x_p - 1 个同向的边或者或者全选同向的边然后取相反的度即可。

然后扩展到一般情况。考虑其实一般的情况构成圆方树。我们依旧从任意的根开始定向。发现给一个圆点定向其实相当于确定了其所有方点对应的二分图中边的方向。那么递归到下面的时候仍旧只有父亲方点被定了向，仍旧可以构造出一组合法的解。

QOJ10272 majority graph

很聪明很聪明一道题。

首先trick1是枚举绝对众数 d，把 a_i = d 看作 +1，其余看作 -1，那么绝对众数是 d 就等价于区间和 > 0。

然后还可以发现，对于某个绝对众数 d，我们只用考虑 a_i = d 的点连向其它点的边，不需要考虑两个 a_i,a_j \neq d 之间的边。也就是我们只需要考虑 a_i = d 的关键点即可。考虑 i 能和 j 连边的条件即为 sum_j \ge sum_i（只有关键点为端点是可以取等号）。

我们就有一个最暴力的做法就是正反枚举两次 i，并枚举 j 暴力连边。

然后就是比较聪明的地方了。我们需要考虑存不存在能直接把一个区间合并起来的情况（只有这样才能做）。

假设我们在考虑关键点 i 向右连的边。可以发现假如 \exists j > i, sum_j > sum_i，对于 \forall l \in [i,j]，我们会这样连边：

所以整个 [i,j] 就是联通的。我们可以找到 \max\limits_{sum_j > sum_i} j 并直接把 [i,j] 合并到一起。转换一下就是求 j 使得 \max\limits_{l > j} sum_l \le sum_i。注意并没有要求 j 是关键点。实际上我们会先通过双指针找到只考虑关键点时 j 的位置，再计算出实际的位置。

然后需要考虑 sum_j = sum_i，考虑直接和 \max\limits_{sum_j = sum_i} j 连边，最后所有 sum 相等的位置都会联通。

CF1062F Upgrading Cities

拓扑序在后的点无法到达拓扑序在前的点，也就是对于一个点 p，（拓扑序在其之前的点是否能到达它）与（拓扑序在其之后的点是否能到达它）是独立的。

故对于一个关键点 p，找出拓扑序小于等于它的点在原图上的导出子图，则这个子图只能有一个0出度的点 p；找出拓扑序大于等于它的点在原图上的导出子图，则这个子图只能有一个0入度的点 p。

如果是半关键点，那两个子图中允许存在最多一个0度的点。并且删掉这个点不能产生新的0度点，及不能有1度点和它相连。记录一下即可。

P9829 Traveling Merchant

先转化一下题意。有无尽路径必然有环，且这个环必须是一圈异色边加一条同色边。所以就是要判断能否从起点走到这样的环上。

具体来说对于一对同色点 (x,y)，我们要找一条从起点开始，只走异色边的点不相交路径，依次经过这两个点。

先说结论：存在这样的路径 \Leftrightarrow 对应的 x,y 的方点父亲是祖先关系

先必要性。我们先走到 x，那么从 x 走到 y 所在子树里一定有至少两条点不相交路径（点双性质），于是一定可以选一条和从起点走到 x 不相交的路径走到 y 所在子树里。

然后充分性，证逆否。不是祖先关系证明他们在其lca的两个子树里。假设我们先走到 x，那我们走进 x 所在的子树里就无法再回到lca，否则从 x 到 lca 的路径就可以被合并成一个点双。也就是我们没法走出来到达 y 了。

建出圆方树判祖先即可。

CF475E Strongly Connected City 2

可以先缩边双。边双树边定叶向，返祖边定根向，对于任意点对 (a,b) 一定存在 a\rightarrow lev \rightarrow rt \rightarrow b 的路径。

然后考虑给缩出来的树上的边定向。首先结论是，对于任意的根 rt，删掉以后会产生若干连通块。一个连通块中的边的方向一定一致。证明就是调整法。考虑反向连通块中的一个子树，子树内部贡献不变，但是可以和连通块中其它点产生贡献。

但是各个连通块到 rt 的边方向不一定。于是我们做一个背包（对。）就可以求出连通块两两贡献的最大值。

枚举 rt，bitset优化背包，复杂度为 O(\frac{n^2} w)

CF1338E JYPnation

竞赛图的一些性质。

首先竞赛图每两个点之间都有连边。思考时请牢记。

大概画一下图，可以玩出来答案只有1，2，3和inf。

考虑如何统计inf。有一个重要性质就是，竞赛图一定是长成一堆单点scc最终连向一个大的scc。考虑先找出一条哈密顿路径，然后考察每个点，将其出边中dfn最小点及其所有后继加入点集，就能构造出这个scc。那么inf的点对就是单点scc中任意两个以及末端scc中的点和所有单点scc。

1就是直接连边的点。

然后考虑2。对于 u\leftarrow v 的点对，若某个点 t_0 使得 u\rightarrow t_1 \rightarrow v，则 t 的任意后继 t_1 一定满足连边方式为 u \rightarrow t_1 \rightarrow v，否则就会连出题目中禁止的形状。也就是说，t_0 一直到最后的强连通分量都要满足连边方式为 u \rightarrow t \rightarrow v。也就是限制最宽松的取法是取末端scc中的点

背包问题

CF1290F Making Shapes

首先考虑确定了每个向量的使用次数，凸包就是唯一的。按斜率顺序加入即可。

假设第 i 个向量使用了 a_i 个，那么能成一个多边形的条件就是：

然后坐标的极差。考虑所有的 x_i > 0 和 y_i > 0 一定在凸包中是连续的。所以极差就是 \sum\limits_{x_i \ge 0} a_ix_i 和 \sum\limits_{y_i \ge 0} a_iy_i

然后问题就变成了求 {a_i} 方案数满足上面两个限制。

这里考虑使用类似倍增的做法。枚举每个 a_i 的第 d 位是否填1，并考虑 \sum a_ix_i 的向上进位。前两个限制要求每一位的数值都相等。极差的限制要求 \sum a_ix_i 最终小于 m，可以额外记录一个变量表示前 d 位是否小于 m

每次 \sum a_ix_i 的进位是 O(nV) 的，其中V = \max |x_i|。于是可以采用记忆化搜索。将四个数的进位和与 m 的大小关系全都写进状态里。

CF1856E2 Permutree

easy ver的做法：考虑将点 p 的子树分成两个集合，代表其中取值 > p 或 < p。最大化 (\sum\limits_{v \in S} siz_v)(\sum\limits_{v \notin S} siz_v)。其实就是要用 siz_v 拼出一个离 \frac 1 2 (siz_p - 1) 最近的数。单次 O(n) 跑01背包即可。

hard ver的做法：将单次背包的复杂度优化到 O(\frac {\sqrt n} w)

考虑根号分治。对于 siz_v > \sqrt {siz_p}，由于 siz_p = 1 + \sum siz_v 所以这样的 siz_v 不超过 \sqrt {siz_p} 个。而对于 siz_v \le \sqrt{siz_p} 我们直接当作多重背包二进制捆绑处理。

考虑一个物品 v 对于 f 数组的影响是使它或上它自己平移 v。考虑使用bitset处理。

P9140 [THUPC 2023 初赛] 背包

奇妙的同余最短路问题。

先贪心地全部取性价比最高的物品 k。那我们可以先选出 m = \lfloor \frac V {v_k} \rfloor w_k

以 v_k 为模数。

然后我们需要求出达到余数 r 最少需要做出多少牺牲 f_r。具体的说，按如下方式建边：

解释：加入物品 x 后会加上 w_x 的贡献。然后为了使得体积不超过 V，需要替换掉 \lfloor \frac{i + v_x}{v_k}\rfloor 个 k 物品。

求最长路即可。

然而我们不能直接跑SPFA。

再观察一下这个建边方式。发现物品 x 的边构成了 \gcd (v_x,v_k) 个环。我们只需要遍历两遍这个环，就可以把所有可能的最短路松弛出来。这部分是 O(nv_k) 的。

那么正确性也就有保障了。由于我们选的是性价比最高的点作为基准建的图，所以必定不存在正环（不然你走一圈用别的物品替换掉性价比最高的物品结果还更优了就比较流汗）。所以最长路是 O(v^2) 级别的。又保证了 v^2 < V，所以我们一定能用小于 V 的代价拼出一个余数 r。

Gym101064L

完全背包，但背包容量 m \le 10^9

记 W = \max w_x

由于物品的选取完全没有限制，我们一定可以把选取集合 S 划分成两个可相交的集合 A 和 B，满足 |\sum\limits_{x \in A} w_x - \sum\limits_{x \in B} w_x| \le W。

可以用这样的两个集合拼出 S 的状态 f(S)：

具体的来说，假如我们预处理出了 [\frac {S - W} 2, \frac {S + W} 2] 中的所有状态，就可以 O(W) 地拼出 f(S)。

所以对于一个区间 [l,r]，我们只需要知道 [\frac {l - W} 2, \frac {r + W} 2]，就可以拼出整个区间。那么区间长度 L 每次会下降成 \frac L 2 + W，递推求和一下大概是一个 O(W) 的东西。

递归出口是 l = 1，此时暴力地用完全背包求出答案即可。然后需要注意的是我们最后的区间 [l,r] 可能比 W 要大，也就是我们需要多预处理一些答案。

NAIPC2016H Jewel Thief

01背包，但是背包体积 m \le 10^5。

考虑体积 \le 300，可以将同一体积的物品打包。

对于第 i 种体积的物品，假如将所有模 i 同余的位置拿出来赋予连续的编号，那我们有如下方程：

其中 val(k,j) 表示第 i 种体积的物品中价值最大的 j - k 个的价值和。

发现 val(k,j) 满足四边形不等式（交叉大于包含），故具有决策单调性。

我们可以通过分治实现 O(m \log m) 进行单次转移。

具体来说，假设我们现在要求所有 j \in [l, r] 的最佳决策。考虑先暴力遍历区间求出 j = mid 时的最佳决策 p，那么 j \in [l, mid) 的最佳决策不大于 p；j \in (mid, r] 的最佳决策不小于 p。在分治时同时记录当前可能成为最佳决策的位置的上下界 [x,y]，递归处理即可。

计数专题

CF1864H Asterism Stream

先转化题意一步。依题意，\{x_1...x_k\} 是一个随机过程，我们要求达到 x_k \ge n，步数的期望就是 \sum\limits_x \sum\limits_i P(x_i = x)。记 f_x 为 \sum\limits_i P(x_i = x)，即 x 出现的概率，则我们要求的就是 \sum\limits_{x = 1}^{n - 1} f_x

考虑转移。我们有：

考虑若 i/2 是偶数，则可以把 f_{i/2} 继续展开，得到

假设 low(i) = k，则

也就是我们保存向量 [f_{i}, f_{i/2}...f_{i/\log i}]，就可以用矩阵优化转移。

记 F_{k} 为 low(i) = k 时的转移矩阵，G_{k} = \prod\limits_{i = 1}^{2^k} F_{low(i)}，H_{k} = \prod\limits_{i = 1}^{2^{k + 1}- 1} F_{low(i)}。

因为我们有性质：x < 2^k 则 low(x) = low(x + 2^k)，所以有转移 G_{k} = G_{k-1}F_{k}，H_{k} = H_{k-1}G_k。（注意左右乘！）同样因此，我们的答案可以对于ans拆位计算。

P12445 [COTS 2025] 数好图 / Promet

先分点为四类

1. 在 1\rightarrow n 上的
2. 能从1到达但是到不了 n
3. 能到 n 但是不能从 1 到达

合法的连边方式有 1\rightarrow 1,1 \rightarrow 2, 2 \rightarrow 2, 3\rightarrow 1，3\rightarrow 3。发现在考虑二、三类点时不用考虑一类点内部连接方式，考虑分着计算。

设 f_{i,j} 为考虑前 i 个点中有 j 个二类点，剩下都是一类点，且不考虑一类点内部连接方式时的方案数。根据上面的连边方式可以给出如下转移：

同样设 g_{i,j} 为考虑前 i 个点中有 j 个三类点，剩余都是一类点，且不考虑一类点连边情况的方案数。转移：

然后考虑一类点的情况。其实就是 k=n 的情况。考虑设计 h_{i,j} 为在前 i 个点中钦定 j 个出度为0的点的连边情况。那么有转移：

然后我们容斥一下，就得到了总共有i个点时恰好只有n为零出度点的方案数：

最后的答案如下计算：

P9563 [SDCPC 2023] Be Careful 2

容斥原理。

枚举包含在正方形内部的禁止点集 S，求包含矩形\{(\min x, \min y), (\max x, \max y)\} 的正方形的面积之和。可以做到 O(2^k)。

考虑减少冗余。观察加入一些在矩形内部的点并不会影响贡献。猜测矩形内部不能出现点。

证明：记 S 包含在对应矩形内部的点集为 T，确定矩形边界的点集为 S_0。则对于所有的这样的矩形，贡献为

所以我们只用枚举内部不包含点的集合即可。

考虑枚举横坐标最小和最大的点 p,q\space(y_p\le y_q)，则 S 的纵坐标下界只能取 p 或者 \{(x_i,y_i)|x_i \in [x_p,x_q]\} 中 p 的前驱。上界同理。所以这样的集合只有 O(k^2) 个。

现在只需要考虑如何计算严格包含矩形 \{(x_1,y_1),(x_2,y_2)\} 的正方形的面积和。考虑枚举边长 d，限制正方形左下角 (x_0,y_0) 的位置区间。

依题意，x_0 \in [0, n - d], x_0 \in [x_2-d+1,x_1 - 1]。在两区间都不为空时一定有交。所以x_0 \in [\max(0,x_2-d+1),\min(n-d,x_1-1)]。y_0 同理。

最后的面积是 \sum\limits_{d} d^2(\min(n-d,x_1-1) - \max(0,x_2-d+1)+1)(\min(m-d,y_1-1)-\max(0,y_2-d+1) + 1)

现在考虑两个括号的分段情况。为了方便，我们令 x_2 := x_2 + 1, x_1 := x_1 - 1

则第一个括号变成 (\min(n - d, x_1) - \max(0, x_2 - d) + 1)。

第一段是 x_2 - d > x_1，即第二个区间为空。这种情况的贡献是 0；

第二段是 x_2 - x_1 \le d < \min(x_2, n - x_1)，此时的贡献是 x_1 - (x_2 - d) + 1 = d + x_1 - x_2 + 1；

第三段是 \min(x_2, n - x_1) \le d < \max(x_2, n - x_1)，即min和max的其中一个跨越了断点。若min先跨越了断点则 n-x_1 \le x_2，即 n-x_2 \le x_1，贡献为 n-d-(x_2-d)+1 = n-x_2；若max先跨越了断点则贡献为 x_1 + 1。容易发现贡献为 \min(n-x_2,x_1)+1

第四段是 \max(x_2, n - x_1) \le d < n，即跨越了两个断点。此时的贡献为 n-d+1

第五段是 n \le d，贡献是0

Gym102411D Double Parlindrome

大概写一下证明过程。

先给出定义：定义本原串为单回文串或只有一种划分方式的双回文串

结论1：若双回文串存在至少两个划分方式，则它存在本原串真循环节。

证明：

设两种划分方式分别划分出了 s[1,p] 和 s[1,q] \space (p < q)，则因为两串回文，所以s[q - p + 1, q] = s[1,p]，即 s[1,p] 是一个border。那就有 len = q - p 为一个周期。记 l = q \bmod len，截取 s_l = s[q - l + 1, q]，则因周期有 s_l = s[1,l]，又因回文有 s_l^R = s[1,l]，所以 s_l 回文。同理可得 s[q - len + 1, q - l] 回文，故 s[p + 1, q] 可以划分为两个回文串。

同理 s[p + 1,|s|] 存在周期 s[p+1,q]，同理取 r = (|s| - p) \bmod len，则同理 s[p + 1, p + r] 回文，那么 s[p+1,q] 又可以被划分为两个回文串。

继续递归处理 s[p+1, q]。假如 s_l = s_r = 0 或者 l + r = len，就证明 s[p+1,q] 已经是一个循环节了。可以退出。

结论2：不同本原串复制出的串不交。

证明：

假如有交，设两个本原串 s_{1,2} 长度分别为 p,q，则 s_3 = s_1[1,\gcd(p,q)] 是两串真周期，且至少有一个串重复了 s_3 两遍以上（我们不认为 s_3s_3 是本原串）。

若 s_1 的唯一划分不在中间，假设在 i，则 |s_1| - i 也可以是一个划分。

若 s_1 的唯一划分在中间，则说明 s_3 重复若干次回文，则说明 s_3 回文。那显然有多种划分方式。

计算时先算出长度为 i 所有的双回文串 f_i，然后算出长度为 i 的所有本原串 g_i，则答案为 \sum \lfloor \frac n i \rfloor g_i

P10013 Tree Topological Order Counting

其实并非特别简单（）

考虑如何计算点 x 的答案。x 的子树中的点肯定在 x 的后面。我们需要计算子树补中在 x 前面放 i 个点的方案数 f_{x,i}。则答案为 \sum {f_{rt, i}}b_{i+1}

考虑转移。其实是一个树上背包。

第一个组合数意为将 v 子树中排名在 x 之前的点插入到 u 子树的序列中，第二个组合数意为将排名在 x 之后的插入序列。C 意为 u 子树中除去 v 子树后的合法拓扑序个数。

记 g_p 为 p 子树中的拓扑序个数。则有转移：

即我们先认为同一子树中的点相同，算一个多重集排列，然后再乘上每个子树内部的排列方式。

单次 O(n^2)，然而我们需要对于所有 x 都做一次，炸了。

注意到这个转移与方向无关，相当于“计算一段路径上的权值乘积”。也就是我们其实可以自顶向下DP。此时状态意味着 p 子树中有 i 个在子树中某个点前的方案数。等我们真的走到这个点了，f_{p,0} \times g_p 即为答案。