← 返回题目列表

AtCoder · dwacon5th_prelims_c

C. k-DMC 子串

中文机器翻译题面 查看原题

分数: 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