题目链接：http://www.bnuoj.com/bnuoj/problem_show.php?pid=29140
题意：一个长度为n的01序列，每次出现1的概率为p。对于连续的x个1得分为1+2+……+x。求得分期望。
思路：设dp[i][j]表示长度为i的序列后j个全部是1的概率，那么有：
这是个O(n*n)的。手算前几项看看规律。令f[i]表示递推到长度为i的序列的得分，ans[i]=f[1]+f[2]+……f[i]。
f[0]=0 dp[0][0]=1
f[1]=p dp[1][0]=1-p,dp[1][1]=p
f[2]=(1-p)*p*1+p*p*2=p+p*p dp[2][0]=1-p,dp[2][1]=(1-p)*p,dp[2][2]=p*p
f[3]=(1-p)*p*1+(1-p)*p*p*2+p*p*p*3=p+p*p+p*p*p
因此推测：f[i]=sum(p^k)(1<=k<=i)，那么ans[i]=ans[i-1]+f[i]，进而得到：ans[n]=sum((n+1-i)*p^i)(1<=i<=n)，得到O(n)的。
现在回想一下，还有一些问题：
（1）为什么上面的dp[i][0]=1-p？
（2）对于n=3的111貌似我们是得到p*1+p*p*2+p*p*p*3，而实际是p*p*p*6?
（3）前面的每个位为什么不考虑后面的位是0还是1？
下面以n=3为例说明以上问题。
000
001
010
011
100
101
110
111
那么，枚举到第一位时我们得到f[1]=p，对于我们这里，也就是后面四个的第一位1对答案的贡献是p，其实最后来看，后四个的第一个1对答案的贡献是：p*(1-p)*(1-p)*1+p*(1-p)*p*1+p*p*(1-p)*1+p*p*p*1，合并同类项化简得到还是p，也就是说对于（2）问题中的p*1+p*p*2+p*p*p*3中的p*1不仅仅只对111的贡献，而是对100、101、110、111四个数第一个1的贡献和。由p的推导也可以看出对111的贡献是p*p*p*1；同理第二位上的1对答案的贡献是1*(1-p)*p*(1-p)+1*(1-p)*p*p+2*p*p*(1-p)+2*p*p*p=p+p*p。那么此时对于111中的贡献是p*p*p*2，其实111的得分还是p*p*p*6。这样我们就说明白了（2）（3）两个问题。我们以第三位上的1为例。分别是001、011、101、111。对001和101来说是一样的，都是1，那么这个1就是(1-p)*(1-p)*p+p*(1-p)*p=(1-p)*p，所以在i=2的时候将dp[i][0]设为1-p。
int n; double p; int main() { rush() { RD(n); RD(p); int i; double ans=0,temp; if(p==1) ans=1.0*(n+1)*n/2; else { temp=1; FOR1(i,n) { temp*=p; ans+=(n+1-i)*temp; } } PR(ans); } return 0; }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230037.html原文链接：https://javaforall.net
![javascript 暂时性死区[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
