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

· · 题解

我的做法很迷，但复杂度应该是对的，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