朝田诗乃 的博客

朝田诗乃 的博客

题解 P5498 【[LnOI2019]脸滚键盘】

posted on 2019-08-10 10:23:44 | under 题解 |

我们发现,每一次的答案乘上区间数量的值形如:

$$a_{i}+a_{i}a_{i+1}+a_{i}a_{i+1}a_{i+2}+...+a_{i+1}+a_{i+1}a_{i+2}+...$$

根据题意,我们设 $Ans_{k}$ 为真正的答案乘上区间数量的值,则有:

$$Ans_{k} = \sum_{i=l}^{r}\frac{sum[r]-sum[i-1]}{mul[i-1]}$$

其中:

$$mul[n]=\prod_{i=1}^{n}a_{i}$$ $$sum[n]=\sum_{i=1}^{n}mul[i]$$

拆开化简有:

$$Ans_{k} = sum[r]\cdot\sum_{i=l}^{r}\frac{1}{mul[i-1]} - \sum_{i=l}^{r}\frac{sum[i-1]}{mul[i-1]}$$

对于后面我们前缀和处理,前面前缀和处理 $\frac{1}{mul[i]}$ 的前缀和即可。区间的数量易证得 $Cnt=\frac{len*(len+1)}{2}$ ,最后除一下就可以了。

注意模数是 $1e8+7$ 。

朝田诗乃:“一个优秀的长脖子鹿是会数数字的位数的。”

代码:

#include <bits/stdc++.h>
const int MAXN = 1000050, P = 1e8 + 7;
void read(int &x) {
    char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
    while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int power(int a, int b) {
    int res = 1;
    for(; b; b >>= 1, a = 1ll*a*a%P) if(b & 1) res = 1ll*res*a%P;
    return res;
}
int mul[MAXN], sufmul[MAXN], n, a[MAXN], sdivm[MAXN], invm[MAXN], q, inv[MAXN];
int main() {
    read(n); read(q); mul[0] = invm[0] = sdivm[0] = sufmul[0] = 1;
    for(int i = 1; i <= n; ++i) read(a[i]);
    for(int i = 1; i <= n; ++i) mul[i] = 1ll*mul[i-1]*a[i]%P;
    for(int i = 1; i <= n; ++i) inv[i] = power(1ll*i*(i+1)%P, P-2), invm[i] = (invm[i-1]+power(mul[i], P-2))%P;
    for(int i = 1; i <= n; ++i) sufmul[i] = (sufmul[i-1]+mul[i])%P;
    for(int i = 1; i <= n; ++i) sdivm[i] = (sdivm[i-1]+1ll*sufmul[i]*(invm[i]-invm[i-1])%P)%P;
    for(int l, r; q--; ) {
        read(l); read(r);
        printf("%d\n", (1ll*sufmul[r]*(invm[r-1]-(l-2<0?0:invm[l-2])+P)%P-(sdivm[r-1]-(l-2<0?0:sdivm[l-2])+P)%P+P)%P*2*inv[r-l+1]%P);
    }
}