题解

思路推导

一个字符串能够重新排列成 $k$ 重串，当且仅当每种字符的出现次数都能被 $k$ 整除。必要性显然；反过来，把每种字符的数量都除以 $k$ 后组成字符串 $t$，就能把原串重新排列成 $t^k$。

对每个前缀维护 26 种字符出现次数模 $k$ 的向量，记位置 $i$ 的向量为 $p_i$，其中 $p_0$ 是全零向量。子串 $s_{l\ldots r}$ 中每种字符的数量都能被 $k$ 整除，当且仅当 $p_{l-1}=p_r$。

于是询问 $[x,y]$ 的答案，等于状态序列 $p_{x-1},p_x,\ldots,p_y$ 中相等状态的无序对数量。若某个状态出现 $c$ 次，它贡献 $c(c-1)/2$。

做法

当 $k=1$ 时，每个子串都合法。长度为 $L$ 的询问答案为 $L(L+1)/2$。

在较小范围内，可以对每个询问重新扫描 $p_{x-1}\ldots p_y$，用频次数组统计相等对。加入一个已有频次为 $c$ 的状态时，答案增加 $c$。

一般情况下，先把所有 26 维前缀向量离散化为整数状态，再把每个询问转成状态数组上的区间 $[x-1,y]$。使用莫队调整当前区间，并维护各状态频次和相等对数量。加入状态时先把当前频次加入答案再递增；删除状态时先递减再从答案中减去新频次。

正确性证明

由字符计数整除的充要条件，子串 $s_{l\ldots r}$ 合法当且仅当其两端前缀模向量相等，即 $p_{l-1}=p_r$。所以每个合法二元组 $(l,r)$ 唯一对应询问状态区间内一对下标 $(l-1,r)$，且这两个下标状态相等；反之，每对相等状态下标也唯一给出一个合法子串。

莫队始终维护当前状态区间中每个状态的精确频次。频次从 $c$ 变为 $c+1$ 时新增 $c$ 对，从 $c$ 变为 $c-1$ 时减少 $c-1$ 对，故维护值始终等于所有状态的组合数之和。按每个询问的目标区间读取该值，即得到所求答案。

复杂度分析

前缀状态构造与离散化的期望时间复杂度为 $O(26n)$。莫队部分的时间复杂度为 $O((n+q)\sqrt n)$，空间复杂度为 $O(26n+q)$。