P1654 OSU!
题目描述
osu 是一款群众喜闻乐见的休闲软件。
我们可以把osu的规则简化与改编成以下的样子:
一共有(n)次操作，每次操作只有成功与失败之分，成功对应(1)，失败对应(0)，(n)次操作对应为(1)个长度为(n)的(01)串。在这个串中连续的 (X) 个 (1) 可以贡献 (X^3) 的分数，这(x)个(1)不能被其他连续的(1)所包含（也就是极长的一串(1)，具体见样例解释）
现在给出(n)，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。
输入输出格式
输入格式：
第一行有一个正整数(n),表示操作个数。接下去(n)行每行有一个([0,1])之间的实数，表示每个操作的成功率。
输出格式：
只有一个实数，表示答案。答案四舍五入后保留1位小数。
其实有一个卷积的想法，注意到如果普通的(f_{i,0/1})转移的话发现(1)的转移是(1^3,2^3,dots)什么的和(prod p)什么的错位的在弄，但是我猜会爆精度。
事实上这个题在求连续1长度的三次方的期望，考虑先求出连续1长度1次方和2次方的期望，然后递推过来
设(a_i)代表前(i)位第(i)位为(1)的长度的期望
即在末尾长度+1，成功的概率是(p_i)
然后(b_i)代表前(i)位第(i)位为(1)的长度的平方的期望
因为期望是线性的，所以可以直接按式子(x^2->x^2+2x+1)延伸贡献
形象点理解，其实这个两个式子求的都是(00dots00111dots11)这样的东西的期望。
然后延伸到立方其实是差不多的，但是为了统计答案需要稍微变形一下，(ans_i)代表前(i)位的答案
(ans_{i-1}=c_{i-1}+oth_{i-1})，事实上第一个式子应该这么拆开看，前面(c_{i-1})是末尾极长(1)的答案，通过期望线性的方法和上面一样进行累加，(oth_{i-1})的第(i-1)位是(0)，但它一样需要乘一下概率，后面的就是延长失败累加答案了。
化简一下式子就成了
Code:
#include <cstdio>
const int N=1e5+10;
double a[N],b[N],c[N];
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)
{
double p;scanf("%lf",&p);
a[i]=(a[i-1]+1)*p;
b[i]=(b[i-1]+2*a[i-1]+1)*p;
c[i]=c[i-1]+(3*b[i-1]+3*a[i-1]+1)*p;
}
printf("%.1lf
",c[n]);
return 0;
}
2019.1.13