CRT 竟然只要求模数互质，赛时受 exLucas 影响以为 CRT 要求模数都是质数（

这下致敬 K8 了

A

懒得喷

B

扫描字符串，维护 \(c_i\) 表示到当前扫到的位置为止，有多少种字符串的最后一次出现左端点在 \(i\)，

则询问 \([l,r]\) 的答案即为扫到 \(r\) 时 \([l,r]\) 的区间和。复杂度 \(O(n^2+q)\)。

C

对于能拼出的串 \(s\)，考虑在其最长的，是给出的串的前缀的，前缀，处统计贡献，这样每种串只被统计一次，

建出前缀 Trie，对于每个节点 \(u\)，若 \(u\) 没有 \(c\) 孩子，则 \(u\) 拼上任何一个以 \(c\) 开头的后缀形成的串都应该在 \(u\) 处统计贡献，

再建个反串前缀 Trie 对每个 \(c\) 统计出以 \(c\) 开头的后缀种类数，用上面的方法统计贡献即可。

D

模数小的话，只需要在线段树的每个节点上维护 \(f_i\) 表示 \(i\) 通过这个节点后会变成什么。

这题给的模数分解成 \(\prod p_i^{k_i}\) 之后 \(p_i^{k_i}\) 都很小，所以以每个 \(p_i^{k_i}\) 为模数求出答案后再 CRT 合并即可。