OSU!
首先,由题可知,本题是个期望题,根据期望的套路,定义f[x]为x前的答案,所以最终答案就是f[n]
f[x]表示前x期望答案,即每一段的长度立方和的期望(一定要清楚)
但是三次方不好算,由于期望有一些特殊的性质,所以我们引入g[x]和k[x]
g[x]表示前x最后期望长度为g[x],k[x]表示前x最后长度平方的期望为k[x](一定要清楚定义)
g[x]的转移即为g[x]=(g[x-1]+1)*p[x](因为是最后的长度,所以必须乘p[x])
k[x]的转移即为k[x]=(k[x-1]+2*k[x-1]+1)*p[x]
————————————————————————————————————————————————————
本题提供了一种很好的构造期望转移方程的方法,如f[x]可以表示从x中选两个人(可以重复,并且(a,b),(b,a)算两种方案),这里的选有别于题目中的成功
则因为最后一个必须成功才有贡献,所以先乘p[x],然后可以选最后一个人x,则另一个人要在x-1个人中选,即为g[x-1]
也可以不选最后一个人x,而在前面选两个人,即为k[x-1]
————————————————————————————————————————————————————
f[]的统计和k的差不多
不同之处在于f[]不一定要选最后一个
所以就是在x个人中随意选出3个人(这里的选不同于题)
则最后一个人不成功是可以的,此时最后一个人的只能是前面有贡献,即为f[i-1]
以下的都必须要最后一个成功,(否则就不能和前面的构成贡献了)
选的时候最后一个人选一次(因为是无序的,所以选的三个名额每个都可以给最后一个人),此时为k[x-1]*3*p[x]
选的时候最后一个人可以选两次(3个名额中选2个名额,还是3种情况,所以还要乘3) ,此时为g[x-1]*3*p[x]
还可以三个名额都给最后一个人,即为1,贡献为p[x]
最新文章
- 用flashfxp做ftp镜像同步
- secureCRT会话导入到xshell中的方法
- 程序设计入门——C语言 第7周编程练习 1多项式加法(5分)
- VS2012配置使用ICE通信接口
- Pydev Debugger not working with breakpoints
- Unity 跑酷Demo难题总结
- duplicate symbol _OBJC_CLASS 错误处理方法
- Redis的安装、配置 --转载
- 简单的实现QQ通信功能(三)
- phpmyadmin自增字段
- 理解class.forName()(转)
- 第八十四节,css布局小技巧及font-awesome图标使用
- css布局与盒子模型
- Fortran与C混合编程(转自Ubuntu)
- Java :BufferedWriter类和BufferedReader类的构造方法、主要方法
- Memcached统计命令
- [原创]K8Cscan插件之Mysql密码爆破
- Coursera Deep Learning 2 Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization - week1, Assignment(Initialization)
- C++中构造函数和析构函数的调用顺序
- 【30集iCore3_ADP出厂源代码(ARM部分)讲解视频】30-12底层驱动之液晶画点驱动