题解 P1654 【OSU!】
fdfdf
·
·
题解
这道题目最后的式子看上去是很简单的，不到10行就码完了，但是求式子的过程并没有那么简单。
很容易想到一种枚举思路:
因为每一段连续的1都有一个结束位置，我们从左到右枚举这个结束位置，
再枚举在这个位置结束的连续的1的长度，最后把贡献加入答案。
用式子写出来就是:
\sum_{i=1}^{n}\sum_{j=1}^{i}p_{i,j}j^3
其中p_{i,j}表示结束位置为i的连续1串，其长度为j的概率
如何做到$O(n)$?考虑**差分**
我们先从一个简单的问题开始
现在你有一个取值为$[1,a]$的整数随机数$x$，它取$i(1\le i\le a)$的几率为$p_i$,求$E(x)
注意这里的p和前面的有所不同
根据数学知识我们知道E(x)=\sum_{i=1}^{a}i\times p_i
现在我们把这个求和式子做一下变换:
\sum_{i=1}^{a}i\times p_i=\sum_{i=1}^{a}\sum_{j=1}^{i}p_i=\sum_{i=1}^{a}\sum_{j=i}^{a}p_j
第一个等号显然
第二个等号交换了一下求和的顺序(如果不知道为什么的可以手画一下a较小的情况)
我们记\sum_{j=i}^{a}p_j=f_i，它表示随机数的取值\ge i的概率
于是我们现在得到了另一个公式:
E(x)=\sum_{i=1}^{a}i\times p_i=\sum_{i=1}^{a}f_i
从另一个角度理解这个式子:
当a=1时,显然E(x)=f_1=p_1
当a=2时,我们如果继续使用f_1=p_1+p_2作为答案,会发现我们把x=2对答案的贡献给算少了;
本来应该是2\times p_2，我们的原答案(f_1)里只有一个p_2
因此我们还要加上一个f_2,即f_1+f_2
当a=3时,我们如果继续使用f_1+f_2=p_1+2p_2+2p_3作为答案,会发现我们把x=3对答案的贡献给算少了;
本来应该是3\times p_3，我们的原答案(f_1+f_2)里只有两个p_3
因此我们还要加上一个f_3,即f_1+f_2+f_3
故每当x的可能取值范围扩大后，我们就需要对于原来我们给出的期望进行补足
回到这道题，我们要算的是\sum_{i=1}^{n}\sum_{j=1}^{i}p_{i,j}j^3
这里的p是前面的p_{i,j}
我们可以换成求f_{i,j}，它表示结束位置为i的连续1串，其长度\ge j的概率
如果我们只要算\sum_{i=1}^{n}\sum_{j=1}^{i}p_{i,j}j(没有了立方)
那么答案变成\sum_{i=1}^{n}\sum_{j=1}^{i}f_{i,j}
而这里的f_{i,j}非常好求，就是\prod_{k=i-j+1}^{i}s_k,
因为**只要$(i-j+1)$到$i$的位置全部为$1$，那么连续1串的长度一定$\ge j$**
如果我们记$x_i=\sum_{j=1}^{i}f_{i,j}$,那么递推式就是
$$x_i=p_ix_{i-1}+p_i$$
这就是大家喜闻乐见的第一个递推式
但是我们现在要算$Ans=\sum_{i=1}^{n}\sum_{j=1}^{i}p_{i,j}j^3
使用前面的补足思想，当x=i+1的时候，x^3需要对之前补足的贡献是(3i^2+3i+1)
因此
Ans=\sum_{i=1}^{n}\sum_{j=1}^{i}p_{i,j}j^3=\sum_{i=1}^{n}\sum_{j=1}^{i}[3(j-1)^2+3(j-1)+1]f_{i,j}
首先记y_i=\sum_{j=1}^{i}j^2p_{i,j}=\sum_{j=1}^{i}[2\times (j-1)+1]f_{i,j}，
由于y_{i-1}\times p_i=\sum_{j=1}^{i-1}[2\times (j-1)+1]f_{i-1,j}\times p_i=\sum_{j=2}^{i}[2\times (j-2)+1]f_{i,j}
故y_i-y_{i-1}\times p_i=\sum_{j=2}^{i}2f_{i,j}+f_{i,1}=2x_{i-1}p_i+p_i
因此y_i的递推式为
y_i=(y_{i-1}+2\times x_{i-1}+1)\times p_i
这就是大家喜闻乐见的第二个递推式
这样我们可以推到次数为3的情况,记
仿照$y_i$的方法我们有大家喜闻乐见的第三个递推式
$$dis_i=(dis_{i-1}+3\times y_{i-1}+3\times x_{i-1}+1)\times p_i$$
使用这三个递推式即可解决问题
虽然这三个递推式并不好理解
但难道我们只是为了$AC$数而做题的吗?
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;dd a[N],x[N],y[N],dis[N];
int main()
{
n=read();
for(RG int i=1;i<=n;i++){
scanf("%lf",&a[i]);
x[i]=(x[i-1]+1)*a[i];
y[i]=(y[i-1]+2*x[i-1]+1)*a[i];
dis[i]=dis[i-1]+(3*y[i-1]+3*x[i-1]+1)*a[i];
}
printf("%.1lf\n",dis[n]);
return 0;
}
```