P10716 [MX-X1-T4] "KDOI-05" Simple String Problem

Original problem link: .

You are given a string $S$. There are $q$ queries. Each query gives $(i, k)$. For each query, find how many non-empty strings $A$ exist such that there are (possibly empty) strings $B_1, B_2, \dots, B_{k-1}$ satisfying: $$S[1,i]=AB_1AB_2A\dots AB_{k-1}A$$ Here, $S[1,i]$ denotes the prefix of $S$ with length $i$.

The first line contains a positive integer $n$, denoting the length of $S$. The next line contains a string of length $n$ consisting only of lowercase letters, denoting $S$. The next line contains a positive integer $q$. The next $q$ lines each contain two positive integers, denoting a query $i, k$.

Output $q$ lines. Each line contains a non-negative integer, denoting the answer.

**Sample Explanation #1** For the first query $(5, 3)$, we can take $A=\texttt{a}$, $B_1=\varepsilon$, $B_2=\texttt{ba}$, where $\varepsilon$ denotes the empty string. It can be proven that there is exactly one valid $A$. **Constraints** **This problem uses bundled testdata.** | Subtask ID | Score | $n,q\leq$ | Special Property | |:--:|:--:|:--:|:--:| | $1$ | $5$ | $500$ | None | | $2$ | $10$ | $5000$ | None | | $3$ | $10$ | $2\times10^5$ | Characters in $S$ are generated randomly from $\tt a,b$ | | $4$ | $20$ | $2\times10^5$ | All queries have the same $k$ | | $5$ | $20$ | $5\times10^4$ | None | | $6$ | $35$ | $2\times10^5$ | None | For $100\%$ of the testdata: $1\leq k\leq i\leq n\leq 2\times 10^5$, $1\leq q\leq 2\times 10^5$, $s$ consists only of lowercase letters. Translated by ChatGPT 5