题解 P5498 【[LnOI2019]脸滚键盘】
皎月半洒花
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}$计算负贡献。
```cdot
#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