自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 22:11:23，当前版本为作者最后更新于2019-08-09 21:09:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我的做法很迷，但复杂度应该是对的，$O(n)$。

首先我们考虑他算的是啥，了解期望是啥的话应该知道重点在求分子，比如当区间长度为$3$时分子应该是这些：

$$a_1+a_2+a_3+a_1a_2+a_2a_3+a_1a_2a_3$$

这东西显然没法直接前缀维护，于是考虑构造一个数列如此递推：

$$F_i=F_{i-1}\cdot a_i+a_i$$

这玩意儿有啥用呢？我们观察$F_3$的展开：

$$\begin{aligned}&\quad~ a_3\\ &+a_3\cdot a_2\\&+a_3\cdot a_2\cdot a_1 \end{aligned} $$

我们可以把它看做一个三角形，其中

$$\begin{aligned}&\quad ~a_2\\&+a_2\cdot a_1 \end{aligned} $$

则是$F_2$

那么其实我们如果换一个简单版本，每次询问都是询问$[1,r]$，那么我们完全可以直接做一个前缀和求出来，因为答案就是$\sum_{i\leq r} F_i$（可以考虑自行验证）。那么现在我们考虑吧如果是算$[l,r]$，我们直接用$S_r-S_{l-1}$是否有错：

首先，减出来之后的$\sum_{i\in[l,r]} F_i$都是从$1$开始推过来的，而不是从$l$。所以我们考虑如下：

$$\begin{aligned}&\quad~ a_3\\ &+a_3\cdot a_2\\&+a_3\cdot a_2\cdot a_1 \\&+a_3 \cdot a_2\cdot a_1\cdot a_0\end{aligned} $$

这是递推好的$F$，现在我们要求$[1,3]$，用前缀和的话，我们发现$a_0$出现在$F_1$中、$F_2$中、$F_3$中，且贡献分别是$a_1\cdot a_0$、$a_2\cdot a_1\cdot a_0$和$a_3\cdot a_2\cdot a_1\cdot a_0$.所以我们需要维护一个前缀积的前缀和乘上$F_{l-1}$计算负贡献。

#define rr register
#define LL long long
#define MAXN 2000100
#define Mod 100000007

using namespace std ; int l, r ;
int Sum[MAXN], S[MAXN], T[MAXN], F[MAXN], base[MAXN] ; int N, M ;

int expow(int a){
    a %= Mod ;
    int res = 1, b = Mod - 2 ;
    while (b){
        if (b & 1)
            res = 1ll * res * a % Mod ;
        a = 1ll * a * a % Mod, b >>= 1 ;
    }
    return res ;
}
inline int qr(){
    int res = 0 ; char c = getchar() ;
    while (!isdigit(c)) c = getchar() ;
    while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
    return res ;
}
int main(){
    int i ; cin >> N >> M, Sum[0] = 1 ;
    for (i = 1 ; i <= N ; ++ i)
        base[i] = qr(),
        Sum[i] = 1ll * Sum[i - 1] * base[i] % Mod,
        F[i] = (1ll * F[i - 1] * base[i] % Mod + base[i]) % Mod,
        S[i] = 1ll * (S[i - 1] + F[i]) % Mod, T[i] = (1ll * T[i - 1] + Sum[i]) % Mod ; T[0] = 1 ;
//    for (i = 1 ; i <= N ; ++ i) cout << Sum[i] << " " ;
    while (M --){
        l = qr(), r = qr() ;
        rr int len = (r - l + 1) ; //cout << T[r] - T[l - 1] << endl ;
        rr int P = (S[r] - S[l - 1] + Mod) % Mod ;
        rr int O = 1ll * (T[r] - T[l - 1] + Mod) * expow(Sum[l - 1]) % Mod ;
        rr int x = (P - 1ll * F[l - 1] * O % Mod + Mod) % Mod ;
        printf("%lld\n", 1ll * x * expow(len * (len + 1) / 2) % Mod) ;
    }
}

后记：并不知道其他大佬怎么做的，但在我看来那个递推式的构造出发点就是加入一个数，会产生多少新贡献这个角度来考虑的orz