我想大声告诉你
description
因为小Y 是知名的白富美，所以自然也有很多的追求者，这一天这些追求者打算进行一次游戏来踢出一些人，小R 自然也参加了。
这个游戏有n 个人参加，每一轮随机选出一个还没有出局的人x，接着x 会出局。x 在出局之后剩下的人会受到一次攻击，每一个人在遭到攻击之后会有p 的概率出局。（注意遭到攻击出局的人是不能攻击剩下的人的）
在所有人都出局之后，遭受攻击次数等于特定值的人能够成为胜者。所以现在小R 想要知道对于每一个0 <= k < n，自己恰好在遭受k 次攻击之后出局的概率是多少。（这里的出局指的不是被攻击出局）
注意在这题中，所有数值的运算在模258280327 的意义下进行。
analysis
-
DP
-
注意每一轮可能有不止一个人被欧中以及被攻击出局，所以计算每一轮不出局的概率没用或者很麻烦
-
首先我们可以把问题转化成一个1−n的排列、这些人依次被欧中或被攻击出局
-
设f[i][j]表示到了第i位，i+1到n都遭受了j次攻击的概率
-
如果是被欧中，那么你会对后面的人都攻击一次，而且你经过j−1次攻击没有死
-
所以f[i][j]+=f[i−1][j−1]∗(1−p)j−1
-
如果被攻击致死，那么你不会有攻击的贡献，而且你经过j−1次攻击没死而第j次死了
-
所以f[i][j]+=f[i−1][j]∗(1−(1−p)j−1)
-
对于每一位的答案j就是n1∑i=0n−1f[i][j]∗(1−p)k
-
由于每个点有n1的概率在某个位置上，所以要乘上n1
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 2005
#define ll long long
#define reg register ll
#define mod 258280327
#define mo mod
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define O3 __attribute__((optimize("-O3")))
using namespace std;
ll f[MAXN][MAXN];
ll inv[MAXN],mi[MAXN];
ll n,x,y,T,p,p1,ans;
O3 inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
O3 inline ll pow(ll x,ll y)
{
ll z=1;
while (y)
{
if (y&1)z=z*x%mod;
x=x*x%mod,y>>=1;
}
return z;
}
O3 int main()
{
//freopen("T2.in","r",stdin);
T=read();
inv[0]=1;
fo(i,1,MAXN-5)inv[i]=pow(i,mod-2);
while (T--)
{
n=read(),x=read(),y=read(),p=(1-x*pow(y,mod-2)%mod+mod)%mod;
memset(f,0,sizeof(f)),f[0][0]=1;
fo(i,0,n)mi[i]=pow(p,i);
fo(i,1,n)
{
fo(k,0,i)
{
f[i][k]=(f[i][k]+f[i-1][k]*((1-mi[k]+mod)%mod)%mod+f[i-1][k-1]*mi[k-1]%mod)%mod;
}
}
fo(k,0,n-1)
{
ans=0;
fo(i,0,n-1)ans=(ans+f[i][k]*mi[k]%mod*inv[n]%mod)%mod;
printf("%lld ",ans);
}
printf("\n");
}
return 0;
}
相关阅读
注意：100*100输出的不是00001，而是1！！！ 做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”
今天怎么来讨论一个话题，那就是网络赚钱。是的，是靠网络来赚钱的工作。因为有些人一听说网络赚钱，第一个反应就是诶，那是骗人的，不可能
作品集对于一个设计师来说很重要，不管是新手设计师还是资深设计师，不管你是找工作还是准备换工作。我们首先要明确的是，作品集最能够
都是做同样的事情，不同的人通过不同的思维就会产生不一样的结果。同样是逛论坛发帖，有的人是为了娱乐陶冶生活情操，而有的人却能利用
客服系统到底应该怎么弄？本文从八个方面详细解说，一起进来看看~客服系统可谓是一款经久不衰的产品，产生时期要追溯至曾经电视购物盛