P8022 [ONTAK2015] Cięcie 解答

题目传送门

题目大意

请提供一个长度为k的数字序列，并指定三个质数p, q, 和r. 即要求将该序列分割成连续的三段子序列"A", "B", 和"C", 每段均不以零开头，并满足以下条件：A能被p整除,B能被q整除,C能被$r整除。

题目分析

不难看出，在确定了 A 和 B 的分界线之后，在每条这样的分界线右侧剩余的部分继续确定所有符合要求的 B 和 C 的分界线。
考虑到参数k的取值范围为 1 \leq k \leq 10^6 ，这种直接的方法可能会导致超时。
因此我们需要改进这一方案以提高效率

依次从前向后扫描 A 和 B 的边界；随后我们从后向前分析 B 和 C 之间的关系。在每一个位置上；我们先去除 R 区域与 C 区域重叠的部分；将剩下的区域定义为 L；并统计其中 L 满足模 q 等于 C 的数量；将其加入最终的答案计算中。整个算法的时间复杂度维持在 O(n) 水平。

除此之外，在题目中的每一个段落都需要特别强调都不含前导 0。对细节部分进行单独处理即可

（这道题细节真的很多，有耐心去做才能做对）

code

    #include<bits/std