题解

思路

一个前缀中若能切成 $q$ 个等比例块，那么整个前缀的 $(D,K)$ 计数是某个最简比例 $(x,y)$ 的 $q$ 倍。沿字符串扫描时，每当同一个最简比例再次出现，就恰好又完整累积了一块该比例。

因此当前答案等于当前最简比例在所有前缀中出现的次数。

做法

维护前缀中 D、K 的数量 $d,k$。对每个位置求 $g=\gcd(d,k)$，把比例归一化为 $(d/g,k/g)$。用映射记录该有序对此前出现次数，先加一，再输出新次数。

当某一计数为零时，最大公约数仍为另一计数，归一化结果自然为 $(1,0)$ 或 $(0,1)$。

正确性证明

若最简比例 $(x,y)$ 在当前前缀是第 $q$ 次出现，则这些出现点的累计计数依次位于同一射线上的递增整数倍。相邻两个出现点之间的字符块计数也为 $(x,y)$ 的正整数倍，所以可以按这些位置切成 $q$ 个比例相同的块。

反之，若能切成 $q$ 个等比例块，每个块计数都是同一最简比例的正整数倍；逐块累加后，每个切点前缀的最简比例都等于整体比例，因此该比例至少出现 $q$ 次。可切块数的最大值恰等于映射中的出现次数，算法正确。

复杂度分析

每个位置进行一次最大公约数和一次映射操作，期望时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

子任务说明

• $n\le18$ 时枚举每个前缀的全部切割方案。
• $n\le3000$ 时可预处理比例后对每个前缀扫描此前所有比例。
• 满数据用频次映射在线计数。