【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$ 的前缀。

第一行一个正整数 $n$ 表示 $S$ 的长度。 接下来一个长度为 $n$ 且仅包含小写字母的字符串表示 $S$。 接下来一行一个正整数表示 $q$。 接下来 $q$ 行，每行两个正整数表示一个询问的 $i,k$。

输出 $q$ 行，每行一个非负整数表示答案。

10
aabaacaaaa
5
5 3
5 2
6 1
10 4
10 5

1
2
1
2
1

10
bababababa
10
6 1
6 2
6 3
6 4
6 5
10 2
10 3
9 4
5 5
4 2

1
1
1
0
0
2
1
1
0
1

**【样例解释 \#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$ 仅包含小写字母。