分数: 600 点
问题陈述
在Dwango Co., Ltd.,有一个名为“Dwango Media Cluster”的内容分发系统,简称为“DMC”。
“DMC”这个名字对 Niwango-kun 来说听起来很酷,所以他开始定义字符串的 DMC 性。
给定一个字符串 S 长度 N 和一个整数 k (k \geq 3), 他定义了 k-DMC 编号 of S 作为三元组的数量 (a, b, c) 满足以下条件的整数:
- 0 \leq a < b < c \leq N - 1
- S[a] =
D - S[b] =
M - S[c] =
C - c-a < k
这里 S[a] 是 a- 字符串的第一个字符 S。索引是从零开始的,即 0 \leq a \leq N - 1 成立。
对于字符串 S 和 Q 整数 k_0, k_1, ..., k_{Q-1},计算 k_i-DMC数量 S 对于每个 i (0 \leq i \leq Q-1).
约束
- 3 \leq N \leq 10^6
- S 由大写英文字母组成
- 1 \leq Q \leq 75
- 3 \leq k_i \leq N
- 输入中给出的所有数字均为整数
输入
输入由标准输入按以下格式给出:
N
S
Q
k_{0} k_{1} ... k_{Q-1}
输出
打印 Q 行。 的 i- 第行应包含 k_i- 字符串的DMC编号 S.
示例输入 1
18 DWANGOMEDIACLUSTER 1 18
示例输出 1
1
(a,b,c) = (0, 6, 11) 满足条件。
奇怪的是,Dwango Media Cluster 按照他的定义并没有那么多 DMC 性。
示例输入 2
18 DDDDDDMMMMMCCCCCCC 1 18
示例输出 2
210
三元组的数量可以计算为 6\times 5\times 7.
示例输入 3
54 DIALUPWIDEAREANETWORKGAMINGOPERATIONCORPORATIONLIMITED 3 20 30 40
示例输出 3
0 1 2
(a, b, c) = (0, 23, 36), (8, 23, 36) 满足除最后一项之外的条件,即 c-a < k_i.
顺便说一句,DWANGO 是“拨号广域网游戏操作”的缩写。
示例输出 4
30 DMCDMCDMCDMCDMCDMCDMCDMCDMCDMC 4 5 10 15 20
示例输出 4
10 52 110 140