【五校联考1day2】JZOJ2020年8月12日提高组T2 我想大声告诉你
【五校联考1day2】JZOJ2020年8月12日提高组T2 我想大声告诉你
题目
Description
因为小Y 是知名的白富美,所以自然也有很多的追求者,这一天这些追求者打算进行一次游戏来踢出一些人,小R 自然也参加了。
这个游戏有n 个人参加,每一轮随机选出一个还没有出局的人x,接着x 会出局。x 在出局之后剩下的人会受到一次攻击,每一个人在遭到攻击之后会有p 的概率出局。(注意遭到攻击出局的人是不能攻击剩下的人的)
在所有人都出局之后,遭受攻击次数等于特定值的人能够成为胜者。所以现在小R 想要知道对于每一个0 <= k < n,自己恰好在遭受k 次攻击之后出局的概率是多少。(这里的出局指的不是被攻击出局)
注意在这题中,所有数值的运算在模258280327 的意义下进行。
Input
第一行输入一个正整数T 表示数据组数。
对于每一组数据输入仅一行三个数n, x, y,表示在这组数据中有n 个人参赛,p = x/y。保证y 和258280327 互质。
Output
对于每组数据,输出一行n 个整数,表示对于k = 0到n - 1 的概率在模258280327 意义下的值。
Sample Input
2
3 40 100
9 32 1049
Sample Output
172186885 92980918 16529941
229582513 163885050 39458156 102374877 116777758 216371874 55544199 95860736 8136787
Data Constraint
对于60% 的数据,n <=100
对于100% 的数据,n <= 2* 10^3^,1 <= T <= 5,0<= x < y <= 10^9^
题解
题意
有\(n\)个人(包括主人公小\(R\))
每一轮会在剩余活人里随机选一个人,让他攻击除他之外的所有活人,然后他挂掉
所有人受到攻击后会有\(p\)的概率挂掉
问主人公小\(R\)经过\(k(0≤k≤n-1)\)次攻击后挂掉(注意不是攻击挂掉,是被抽到挂掉)的概率
分析
易想到概率\(DP\)
容易发现每个人(除小\(R\)外)都是一个\(NPC\),他们挂掉的顺序我们不用在意 (残忍)
那么可以编号
规定第\(i\)个人在第\(i\)轮被抽到
设\(f[i][j]\)表示现在第\(i\)个人要挂掉,第\(i-1\)个人到第\(n\)个人都还活着,每个人都被进攻了\(j\)次
那么转移:
\(f[i][j]+=f[i-1][j]*(1-(1-p)^j)+f[i-1][j-1]*(1-p)^{j-1}\)
解释:
首先\(f[i][j]\)可以从两个方面转移
一是之前被进攻了\(j-1\)次没挂,这次挂了
二是之前进攻都没死,现在被抽到要挂掉了
那么转移方程的前半对应一,后半对应二
自己想一想
答案为
\(Ans(j)=\sum_{i=0}^{n-1}*\dfrac{1}{n}*(1-p)^j\)
转移即可
Code
#include<cstdio>
#include<cstring>
#define mod 258280327
using namespace std;
int t,n,x,y,i,j;
long long p,ans,mdn,pow[2005],f[2005][2005];
long long ksm(long long x,long long y)
{
long long res;
res=1;
while(y)
{
if (y&1) res=res*x%mod;
y>>=1;
x=x*x%mod;
}
return res;
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d%d%d",&n,&x,&y);
mdn=ksm(n,mod-2);
p=(1-x*ksm(y,mod-2)%mod+mod)%mod;
for (i=0;i<=n;i++)
pow[i]=ksm(p,i);
memset(f,0,sizeof(f));
f[0][0]=1;
for (i=1;i<=n;i++)
for (j=0;j<=i;j++)
f[i][j]=((f[i][j]+f[i-1][j]*(1-pow[j]+mod)%mod)%mod+f[i-1][j-1]*pow[j-1]%mod)%mod;
for (j=0;j<n;j++)
{
ans=0;
for (i=0;i<n;i++)
ans=(ans+(f[i][j]*mdn%mod)*pow[j]%mod)%mod;
printf("%lld ",ans);
}
printf("\n");
}
return 0;
}
最新文章
- PAMI 2010 Context-aware saliency detection
- mysql 将列值转变为列的方法(转)
- javascript实现优先队列
- 《JS高程》实现继承的6种方式(完整版)
- Oracle收缩表空间
- Bootstrap框架菜鸟入门教程
- js动态添加、删除行
- Django 中文和时区设置
- SQL 读取XML到Datatable
- 【AGC014E】Blue and Red Tree 并查集 启发式合并
- C++ 中的不定参数与格式化字符串 # ## vsprintf
- [solution] JZOJ 5459. 密室
- node爬虫扒小说
- 【题解】Luogu P4344 [SHOI2015]脑洞治疗仪
- shell快捷方式总结
- 转载mysql数据库配置优化
- #使用ListView更新数据出现闪烁解决办法
- QT样式表
- Web应用程序项目OxiteSite已配置为使用IIS.在本地计算机上找不到服务器
- sql 筛选表中指定字段包含26某个小写字母