AT_dwacon5th_prelims_c k-DMC

Dwango 的内容分发基础系统 Dwango Media Cluster，简称 DMC。 觉得这个名字很酷的“ニワンゴくん”决定将字符串的 DMC 特征定义为一个数值。 具体来说，给定一个长度为 $N$ 的字符串 $S$ 和一个不小于 3 的整数 $k$，我们将满足以下条件的整数三元组 $(a, b, c)$ 的个数称为 $S$ 的 $k$-DMC 数。 - $0 \leq a$ - $S[a]$ 为 `D` - $S[b]$ 为 `M` - $S[c]$ 为 `C` - $c - a < k$ 这里，$S[a]$ 表示 $S$ 的第 $a$ 个字符。字符串的第一个字符编号为 $0$（即 $0 \leq a \leq N-1$）。 对于给定的字符串 $S$ 和 $Q$ 个整数 $k_0, k_1, \ldots, k_{Q-1}$，请分别计算每个 $k_i$ 的 $k_i$-DMC 数。

输入通过标准输入给出，格式如下： > $N$ $S$ $Q$ $k_0$ $k_1$ $\ldots$ $k_{Q-1}$

输出 $Q$ 行。 第 $i$ 行（$0 \leq i \leq Q-1$）输出字符串 $S$ 的 $k_i$-DMC 数。

## 限制条件 - $3 \leq N \leq 10^6$ - $S$ 是由 `A` 到 `Z` 组成的字符串 - $1 \leq Q \leq 75$ - $3 \leq k_i \leq N$ - 输入的所有数值均为整数 ## 样例解释 1 $(a, b, c) = (0, 6, 11)$ 满足条件。 Dwango Media Cluster 按照“ニワンゴくん”的定义，似乎并不太像 DMC。 ## 样例解释 2 有 $6 \times 5 \times 7$ 种组合可能。 ## 样例解释 3 除了 $c-a$ 的条件外，$(a, b, c) = (0, 23, 36), (8, 23, 36)$ 满足条件。 顺便一提，DWANGO 是 “Dial-up Wide Area Network Gaming Operation” 的首字母缩写。 由 ChatGPT 4.1 翻译