P10716 【MX-X1-T4】「KDOI-05」简单的字符串问题

原题链接：。

你有一个字符串 $S$。$q$ 个询问，每次给出 $(i,k)$，求有多少个非空字符串 $A$，使得存在可空字符串 $B_1,B_2,\dots,B_{k-1}$ 满足： $$S[1,i]=AB_1AB_2A\dots AB_{k-1}A$$ 其中 $S[1,i]$ 表示 $S$ 的长度为 $i$ 的前缀。

无

无

**【样例解释 \#1】** 对于第一次询问 $(5,3)$，可以取 $A=\texttt{a}$，$B_1=\varepsilon$，$B_2=\texttt{ba}$，其中 $\varepsilon$ 表示空串。可以证明有且仅有一个合法的 $A$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n,q\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:| | $1$ | $5$ | $500$ | 无 | | $2$ | $10$ | $5000$ | 无 | | $3$ | $10$ | $2\times10^5$ | $S$ 中字符从 $\tt a,b$ 中随机生成 | | $4$ | $20$ | $2\times10^5$ | 每个询问的 $k$ 相同 | | $5$ | $20$ | $5\times10^4$ | 无 | | $6$ | $35$ | $2\times10^5$ | 无 | 对于 $100\%$ 的数据：$1\leq k\leq i\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$，$s$ 仅包含小写字母。