问题

给定一个字符串 $s(1\le |s| \le 10^5)$ ，求最小的 $k$ ，使得存在 $s_1,s_2,\dots,s_k$ ，满足 $s_i(1\le i \le k)$ 均为回文串，且 $s_1,s_2, \dots ,s_k$ 依次连接后得到的字符串等于 $s$ 。

Div. 1 (久违的题解)。

A Feeding Chicken

给定一块 $r \times c$ 的空地，每个格子上可能放着一份猫粮，一共 $k$ 只猫，你现在需要为每只猫分配一个四联通块，使得每只猫得到的猫粮个数极差最小。

显然，可以尽量构造出一种平均的方案，即极差 $\le 1$。一个比较容易的方案是按照蛇形棋的顺序分配。

B Send Boxes to Alice

给定一个序列 $a$，每个位置有 $a_i$ 份猫粮，每次操作可以把一份猫粮从 $i$ 位置移动到 $i+1$ 或 $i-1$，你现在要最小化操作次数，使得整个序列的 $\gcd > 1$。

枚举总猫粮数的因子 $p$，计算使得最终 $\gcd$ 为 $p$ 的倍数时的最小操作次数。枚举每个前缀，计算在模 $p$ 意义下的前缀和 $sum$，代表前面这些位置还未被分配的个数，如果这些个数很少，可以把这些东西统一向后移动一格，否则个数很多时，可以把后面的东西移动到前边，即 $\min(sum,p-sum)$。

C Point Ordering

交互题，猜一个 $n$ 个点凸多边形的顺序，隐藏多边形的点编号不是按照顺时针或逆时针顺序，而是乱序，你现在需要用最多 $3n$ 次询问猜出这个顺序。

你有两种询问，第一种询问一个三角形的面积，第二种询问三个点 $i,j,k$ 的 $\vec{ij} \times \vec{ik}$ 的正负号。

第一步，用 $n$ 次询问找出多边形的一条边。随便选一对点，然后枚举其他点向某一边扩展。

第二步，求出这条边和其他所有点的三角形面积，找到面积最大的三角形的对应顶点。

第三步，确定其他点在上一步这个最大顶点的哪一侧。同一侧高度单调，面积也单调。

D Tree Queries

给定一棵无根树，有两种操作。

1. 输入 $v,d$，从 $n$ 个点中等概率选择点 $r$，然后将所有满足到 $r$ 的路径经过点 $v$ 的点 $u$，权值加上 $d$。

2. 询问 $v$ 的点权期望。

简单推一下修改的贡献，点 $u$ 的期望加 $d$，考虑其每个邻居（包括父亲）的子树大小 $siz$，这个子树内的点权加上 $(n-siz)/n$。

然后一个显然的做法呼之欲出，按度数大小分块，小度数线段树维护，大度数暴力打标记，时间复杂度 $O(n\sqrt{n \log n})$。

修改的瓶颈在于不能枚举一个点的所有度数。考虑树剖，只修改重儿子对应子树，和询问点的子树外的所有点。询问时，只需要计算根到询问点路径上所有轻边带来的贡献，显然只有 $\log n$ 条轻边，时间复杂度 $O(n\log n)$。

题意

给定一棵 $n$ 个点的无根树，每个点有点权，求长度为 $D$ 且满足路径点权的 $\gcd$ 大于 $1$ 的路径个数。

其中 $3 \le n \le 5 \cdot 10^5$，值域 $[1,30000]$。

分析

记 $f(n)$ 表示路径 $\gcd$ 和为 $n$ 的路径数，$g(n)$ 表示路径 $\gcd$ 为 $n$ 的倍数的路径数。

因此有

$$g(d)=\sum_{d|n} f(d)$$

由莫比乌斯反演

$$f(d)=\sum_{d|n} \mu(\frac{n}{d}) g(n)$$

因此答案 $S$ 就是

$$S=\sum_{i=2}^\infty f(i)=\sum_{i=2}^\infty \sum_{i|d} \mu(\frac{d}{i}) g(d)$$

交换求和顺序

$$S=\sum_{d=1}^\infty g(d) \sum_{i>1 \land i|d} \mu(\frac{d}{i}) = \sum_{d=2}^\infty g(d)(0-\mu(d))$$

于是只需要计算 $g(d)$ 即可，枚举值域 $i \in [2,30000]$ 且 $\mu(i) \neq 0$，计算有多少条长度为 $D$ 的路径的点权都是 $i$ 的倍数。将这些点拿出来，显然是这个点集构成一个森林，下面考虑一棵树的情况。记 $dp(u,i)$ 表示以 $u$ 为根节点的子树内距离 $u$ 为 $i$ 的点数。状态数和转移的复杂度都是 $O(n^2)$ 的，套用长链剖分优化关于深度信息合并的技巧，可以做到 $O(n)$ 的时空求出这个 $dp$ 数组。