首页 > 试题广场 >

K串

[编程题]K串
  • 热度指数：2 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
ZZT 得到了一个字符串 S 以及一个整数 K。
WZH 在 1995 年提出了“优雅 K 串”的定义：这个字符串每一种字符的个数都是 K 的倍数。
现在 ZZT 想要对字符串进行 Q 次询问，第 i 次询问给出一个区间 [Li, Ri]，他想计算 [Li, Ri] 中有多少个子串是“优雅 K 串”。
由于 ZZT 忙于工作，所以他把这个问题交给了你，请你帮忙解决。

输入描述:
第一行输入一个正整数 K。
第二行输入一个字符串 S。
第三行输入一个正整数 Q，表示有 Q 次询问。
接下来 Q 行，每行输入两个正整数 Li 和 Ri，表示第 i 次询问。
1 ≤ K ≤ 50.
1≤ | S | ≤ 3 x 104 且 S 仅包含小写英文字母.
1≤ Q ≤ 3 x 104.
1 ≤ Xi ≤ Yi ≤ N.


输出描述:
每次询问，输出一个正整数，表示满足条件的“优雅 K 串”的数量。
示例1

输入

1
abc
3
1 3
1 2
2 3

输出

6
3
3
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

哈希
上传者：牛客301599号
难度：
0条回答 8浏览

热门推荐

通过挑战的用户

查看代码

相关试题

K串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号