Description

因?yàn)樾 是知名的白富美，所以自然也有很多的追求者，這一天這些追求者打算進(jìn)行一次游戲來踢出一些人，小R 自然也參加了。
這個(gè)游戲有n 個(gè)人參加，每一輪隨機(jī)選出一個(gè)還沒有出局的人x，接著x 會(huì)出局。x 在出局之后剩下的人會(huì)受到一次攻擊，每一個(gè)人在遭到攻擊之后會(huì)有p 的概率出局。（注意遭到攻擊出局的人是不能攻擊剩下的人的）
在所有人都出局之后，遭受攻擊次數(shù)等于特定值的人能夠成為勝者。所以現(xiàn)在小R 想要知道對(duì)于每一個(gè)0 <= k < n，自己恰好在遭受k 次攻擊之后出局的概率是多少。（這里的出局指的不是被攻擊出局）
注意在這題中，所有數(shù)值的運(yùn)算在模258280327 的意義下進(jìn)行。

Input

第一行輸入一個(gè)正整數(shù)T 表示數(shù)據(jù)組數(shù)。
對(duì)于每一組數(shù)據(jù)輸入僅一行三個(gè)數(shù)n, x, y，表示在這組數(shù)據(jù)中有n 個(gè)人參賽，p = x/y。保證y 和258280327 互質(zhì)。

Output

對(duì)于每組數(shù)據(jù)，輸出一行n 個(gè)整數(shù)，表示對(duì)于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

對(duì)于60% 的數(shù)據(jù)，n <=100
對(duì)于100% 的數(shù)據(jù)，n <= 2* 10^3，1 <= T <= 5，0<= x < y <= 10^9

分析

我想大聲挖倍內(nèi)聽！吔X啦梁非凡！

內(nèi)！我要炒內(nèi)啊！

↑這是我看到題目一瞬間腦補(bǔ)的

這題意有個(gè)等價(jià)的方法

就是第i次游戲選第i個(gè)人，第i個(gè)人未出局就出局，并且使后面i+1~n個(gè)人有p概率出局，已出局就不管

其實(shí)是一樣的

那么可以寫DP

設(shè)f[i][j]為選第i個(gè)人前，1~i-1有j個(gè)人被點(diǎn)出局了

那么狀態(tài)轉(zhuǎn)移顯然：

1、f[i+1][j+1]+=f[i][j]*((y-x)/y)^(j+1)（i被點(diǎn)掉了）

2、f[i+1][j]+=f[i][j]*(x/y)^(j)（i剛好沒了）

最后求和除個(gè)n就行

?

#include <iostream> #include <cstdio> #include <memory.h> using namespace std; typedef long long ll; const int P=258280327; const int N=2e3+10; int T,n; ll x,y,ny[N],f[N][N];ll Power(ll x,ll y) {ll ans=1;for (;y;y>>=1,(x*=x)%=P) if (y&1) (ans*=x)%=P;return ans;}int main() {for (scanf("%d",&T);T;T--) {scanf("%d%lld%lld",&n,&x,&y);ll cy=Power(y,P-2);ny[0]=1;memset(f,0,sizeof f);f[1][0]=1;for (int i=1;i<=n;i++) ny[i]=ny[i-1]*(y-x)%P*cy%P;for (int i=1;i<n;i++)for (int j=0;j<i;j++)if (f[i][j])(f[i+1][j+1]+=f[i][j]*ny[j+1]%P)%=P,(f[i+1][j]+=f[i][j]*(1-ny[j]+P)%P)%=P;for (int i=0;i<n;i++) {ll lans=0;for (int j=1;j<=n;j++) (lans+=f[j][i])%=P;printf("%lld ",lans*Power(n,P-2)%P);}printf("\n");} } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/mastervan/p/10316836.html

總結(jié)

以上是生活随笔為你收集整理的[概率期望DP]JZOJ 4212 我想大声告诉你的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。