[HDU4652]Dice
2024-10-20 20:57:04
题意
\(m\)面骰子,求
1.连续出现\(n\)个相同的停止;
2.连续出现\(n\)个不同的停止
的期望投骰子次数。
\(n,m ≤ 10^6\)
sol
首先考虑一个转移式子吧。
设\(f_i,g_i\)分别表示已经连续出现了\(i\)个相同/不同时的期望步数:
\[f_i=\frac 1mf_{i+1}+\frac{m-1}mf_1+1
\]
\]
(只有\(\frac 1m\)的概率继续投出对应的颜色,否则就前功尽弃,从\(1\)重新开始)
\[g_i=\frac{m-i}{m}g_{i+1}+\frac 1m\sum_{x=1}^{i}g_x+1
\]
\]
(如果投出了与之前相同的颜色,每种颜色各有\(\frac 1m\)的概率出现,所以各有\(\frac 1m\)的概率退回到\(1..i\)的状态)
边界状态\(f_n=g_n=0\),我们的目标是求\(f_0,g_0\)。
考虑怎么解上面那个东西吧,这里我们用一种很经典的方法——错位相减。
先做\(f_i\)吧。
把\(f_{i+1}\)对应的式子写出来:
\[f_{i+1}=\frac 1mf_{i+2}+\frac{m-1}mf_1+1
\]
\]
两式相减:
\[f_i-f_{i+1}=\frac 1m(f_{i+1}-f_{i+2})
\]
\]
因为有一个很显然的条件式:\(f_0-f_1=1\)
所以就可以直接推得:
\(f_1-f_2=m,f_2-f_3=m^2......f_{n-1}-f_n=m^{n-1}\)
那么\(f_0=\sum_{i=0}^{n-1}m^i=\frac{1-m^n}{1-m}\)
然后是\(g_i\)。
同样把\(g_{i+1}\)对应的式子写出来:
\[g_{i+1}=\frac{m-i-1}{m}g_{i+2}+\frac 1m\sum_{x=1}^{i+1}g_x+1
\]
\]
同样两式相减:
\[g_i-g_{i+1}=\frac{m-i}mg_{i+1}-\frac{m-i-1}mg_{i+2}-\frac 1mg_{i+1}\\=\frac{m-i-1}m(g_{i+1}-g_{i+2})
\]
\]
同样还是根据\(g_0-g_1=1\)的性质可知:
\(g_1-g_2=\frac m{m-1},g_2-g_3=\frac{m^2}{(m-1)(m-2)}......\)
线性递推即可。
时间复杂度\(O(Tn)\)
code
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
int T;
while (scanf("%d",&T)!=EOF)
while (T--)
{
int ty,m,n;scanf("%d%d%d",&ty,&m,&n);
if (!ty)
printf("%.10lf\n",(pow(m,n)-1)/(m-1));
else
{
double ans=0,last=1;
for (int i=1;i<=n;++i)
ans+=last,last*=1.0*m/(m-i);
printf("%.10lf\n",ans);
}
}
return 0;
}
最新文章
- $_SERVER 详情
- atitit.闭包的概念与理解attilax总结v2 qb18.doc
- H5案例分享:移动端touch事件判断滑屏手势的方向
- 【iCore3 双核心板】【发布基于 iCore3的显示模块(包含7寸屏,4.3寸屏,vga模块等】
- MySQL Command 常见命令
- c# 编程语言 编译器 Roslyn
- cocos2d-js取不到cocostudio里面控件问题
- 使用proguard混淆android代码
- Mac添加或修改环境变量
- Roman Roulette(约瑟夫环模拟)
- C# 词法分析器
- SQL TOP分页
- c# 应用NPOI 获取Excel中的图片,保存至本地的算法
- 外部无法捕捉Realm的doGetAuthenticationInfo方法抛出的异常
- PHP数字金额转换大写金额
- 7.桥接模式(Bridge Pattern)
- Maya API Test
- <;TCP/IP>;ICMP报文的分类
- 微软microsoft word的api文档地址
- [Solution] 950. Reveal Cards In Increasing Order
热门文章
- Asp.Net mvc4 项目 在vs中调试正常 在IIS发布后连接oracle数据库时提示数据库连接关闭
- GridView 显示行号 设置行号列的宽度
- 【python】-- 类的实例化过程、特征、共有属性和私有属性
- scala actor编程之对象传递
- 3.22课&#183;&#183;&#183;&#183;&#183;&#183;&#183;&#183;&#183;CSS样式表
- IOS蓝牙开发模块
- Data Structure Array: Maximum circular subarray sum
- python 3 并发编程之多进程 multiprocessing模块
- dsp2812 pwm配置
- Android系统Recovery工作原理之使用update.zip升级过程分析(一)---update.zip包的制作【转】