题解 P6036 Ryoku 爱学习

· · 题解

Problem

求期望能掌握的每一段连续时刻的知识的喜爱程度之和是多少（需要注意的是，这里所说的连续时刻的知识不能被一段更长的所包含）。

f(l,r)=a^{b(r-l)} \sum_{i=l}^r w_i

Solution

不难将题意转化为：

\sum_{l=1}^{n}\sum_{r=l}^{n}a^{b(r-l)}(1-p_{l-1})(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)

注意乘上 l-1，r+1 不选的概率。

前缀和优化+暴力枚举时间复杂度 O(n^2)，

由数据范围可知正解的时间复杂度应是 O(n) 或 O(n\log n)，

因此考虑单独枚举 l，递推求解后面的式子：

\sum_{l=1}^{n}(1-p_{l-1})\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)

简便起见，我们设：

\boxed{f_l=\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)}

考虑如何由 f_{l+1} 推 f_l：

f_{l+1}=\sum_{r=l+1}^{n}a^{b(r-l-1)}(1-p_{r+1})\left(\prod_{i=l+1}^{r}p_{i}\right)\left(\sum_{i=l+1}^{r}w_{i}\right)

先乘上 a^b\cdot p_l：

f_{l+1}\cdot a^b\cdot p_l=\sum_{r=l+1}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l+1}^{r}w_{i}\right)

简便起见，我们设：

g_{l+1}=\sum_{r=l+1}^{n}a^{b(r-l-1)}(1-p_{r+1})\left(\prod_{i=l+1}^{r}p_{i}\right)

乘上 a^b\cdot p_l\cdot w_l 并与上面的式子合并：

f_{l+1}\cdot a^b\cdot p_l+g_{l+1}\cdot a^b\cdot p_l\cdot w_l=\sum_{r=l+1}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)

再加上 r=l 的情况：

g_l=g_{l+1}\cdot a^b\cdot p_l+p_{l}\cdot (1-p_{l+1})

所以

\boxed{f_{l+1}\cdot a^b\cdot p_l+g_{l}\cdot w_l=\sum_{r=l}^{n}a^{b(r-l)}(1-p_{r+1})\left(\prod_{i=l}^{r}p_{i}\right)\left(\sum_{i=l}^{r}w_{i}\right)}

由此我们得到了 f 和 g 的递推式：

f_l=f_{l+1}\cdot a^b\cdot p_l+g_{l}\cdot w_l g_l=g_{l+1}\cdot a^b\cdot p_l+p_{l}\cdot (1-p_{l+1})

回归最初的式子，得到：

ans=\sum_{l=1}^{n}(1-p_{l-1})\cdot f_i

然后你就可以 O(n) 解决这个问题了。

Code

double p[maxn], a, b, z;
int n, w[maxn];

int main() {
    scanf("%d %lf %lf", &n, &a, &b);
    a = pow(a, b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= n; i++)
        scanf("%lf", &p[i]);
    double f = p[n] * w[n];
    double g = p[n];
    for (int i = n - 1; i >= 0; i--) {
        z += (1.0 - p[i]) * f;
        g = g * a * p[i] + (1 - p[i + 1]) * p[i];
        f = f * a * p[i] + g * w[i];
    }
    printf("%lf\n", z);
    return 0;
}

AD

blog