JZOJ 100035【NOIP2017提高A组模拟7.10】区间

时间:2022-12-17 13:54:52

题目大意:

JZOJ 100035【NOIP2017提高A组模拟7.10】区间
1<=k<=n<= 2107
1<=t,p<= 109
time limits:2s

题解:

我们注意到这是没有办法用逆元的。
但就就是这就是分块啊(为毛比赛没有一个人想到)。
把n个序列分成长度为k的若干段,当然最后一段不一定是k。
然后对每一块求一个前缀、后缀乘积和。
最后暴枚区间,注意到每个区间刚好会被两段或一段覆盖,直接O(1)算即可。

这道题最难点在于想到刚好每段是k个,这样查询时刚好只会覆盖两段的前缀、后缀。
如果是k+1、k-1个,还勉强可以。
k+2个,可能就不是前后缀了。
k-2个,可能就覆盖三段了,就是这么巧。

Code: