beijing(数学题)
2024-10-21 03:19:04
beijing(数学题)
甲和乙随机进行2n+1场n胜球赛,赌球必须对每场球赛单独押注。由于小明是甲队的铁杆球迷,现在小明希望如果甲最终获胜,那么他获得\(2^{2n-1}\)元,否则乙队获胜,他失去\(2^{2n-1}\)元。给出所有比赛的结果,如果你是小明,请问如何对比赛押注,才能使得目标被达成。
如果当前甲的胜率是p,那么假设下一场比赛甲赢了,胜率会变成p+q。由于甲赢的胜率和甲输的胜率的平均数是p(待证),因此只要对每场比赛下注\(2q*2^{2n-1}\),最后就能达成目的。设\(F(t, i)\)表示还剩下t场比赛,甲队需要赢i场才能获得最终的胜利,甲队最终获胜的概率。
假设到当前位置,甲还需要x场获得胜利,乙还需要y场获得胜利。如果下一场比赛赢了,胜率会变成\(F(x+y-2, x-1)\),输了则会变成\(F(x+y-2, x)\)。显然的是,\(F(x+y-2, x-1)-F(x+y-2, x)=2q\)。
由F的定义可以推出式子:\(F(t, i)=\frac{2^t-\sum_{0\le j<i}C(j, t)}{2^t}\)。因此\(F(x+y-2, x-1)-F(x+y-2, x)=\frac{C(x-1, x+y-2)}{2^{x+y-2}}=2q\)。因此q可以通过那个分式推出来。
#include <cstdio>
using namespace std;
typedef long long LL;
const LL maxn=1e5+5, P=1e9+7;
LL n, inv[maxn*2], fac[maxn*2], mi2[maxn*2], ans, d, cnt[2];
LL C(LL m, LL n){ //C(m, n)
return fac[n]*inv[m]%P*inv[n-m]%P; }
int main(){
scanf("%lld", &n); inv[0]=inv[1]=1; fac[0]=mi2[0]=1;
for (LL i=2; i<=2*n; ++i) inv[i]=inv[P%i]*(P-P/i)%P;
for (LL i=2; i<=2*n; ++i) inv[i]=inv[i]*inv[i-1]%P;
for (LL i=1; i<=2*n; ++i) fac[i]=fac[i-1]*i%P;
for (LL i=1; i<=2*n; ++i) mi2[i]=mi2[i-1]*2%P;
LL x=n, y=n;
for (;;){
printf("%lld\n", C(x-1, x+y-2)*mi2[2*n-x-y+1]%P);
scanf("%lld", &d);
if (++cnt[d]==n) break;
if (d==0) --x; else --y;
}
return 0;
}
最新文章
- C 标准库系列之float.h
- python征程1.1(初识python)
- asp.net读取execl模板并填充数据,关闭进程
- html给div加超链接的方法
- Tomcat启动服务报错:Unknown version string [3.1]. Default version will be used.
- win-tc图形库编程
- SecureCRT issue ";Could not open clipboard: Assess is denied"; (无法打开粘贴板:访问被拒绝)
- 慕课网-安卓工程师初养成-4-7 Java循环语句之 while
- c# 获取数组中最大数的值
- 社区发现算法问题&;&;NetworkX&;&;Gephi
- 去除 Visual Studio 中臃肿的 ipch 和 sdf 文件
- html 5的localstorag
- Android ActionBar详解(二):ActionBar实现Tabs标签以及下拉导航
- hdu 4888 Redraw Beautiful Drawings 最大流
- 使用nfs作为根文件系统启动,(3)
- IntelliJ Idea 2017 注册码 免费激活方法
- Natas Wargame Level27 Writeup(SQL表的注入/溢出与截取)
- Twisted UDP编程技术
- Nodejs.Electron(Nodejs的图形界面开发)安装和试用
- .net core使用RPC方式进行高效的HTTP服务访问
热门文章
- [转载]rmmod: can&#39;t change directory to &#39;/lib/modules&#39;: No such file or directory
- Java基础--垃圾回收GC
- 机器学习:PCA(人脸识别中的应用——特征脸)
- RDD之一:总体介绍
- 在U盘分区安装Kali并引导live CD 教程以及常见的注意事项
- [MySQL]修改mysql数据库的root密码的方法
- java 字符串和集合互相转换
- myeclipse debug 工具栏不见了
- 配置镜像yum源--解决RHN not available的问题
- js中的控制结构for-in语句