题解 51nod 1850 抽卡大赛

题解 51nod 1850 抽卡大赛

题面

51nod

解析

首先考虑一个较暴力的做法.

枚举每个人,再枚举他抽到的卡,考虑 $\texttt{DP}$ 出这张卡的排名的概率.

设 $f[i][j]$ 表示到了第 $i$ 个人(不计算当前这人),有 $j$ 个人的 $\texttt{A}$ 比他小的概率,则排名为 $n-j$.

将每个人的卡从小到大排序,二分出比当前这张卡小的最大的卡,则概率是一个前缀和除以 $Q$.

则转移方程为:$f[i][j]=f[i-1][j-1]\times p+f[i-1][j]\times (1-p)$,其中 $p$ 是概率.

但是,这个算法是 $O(n^4)$ 的,并不能通过此题.

考虑到每次转移都只需要比当前这张卡小的卡,因此可以把卡按 $\texttt{A}$ 从小到大排序,枚举卡,将答案统计到它属于的人上.

然后考虑到这个方程可以倒推,即由 $f[i][j]$ 推回 $f[i][j-1]$.(具体过程可见代码)

因此每次枚举卡时,我们可以先倒推出没有它所属于的人的情况,即由 $f[n][j]$ 推出 $f[n-1]j$

在统计答案后再将概率更新.

这样求出概率就是 $O(n)$ 的,总复杂度 $O(n^3)$.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=205;
const int M=200005;
const int Mod=1000000007;
struct node{int a,g,p,id;}b[M];
int n,m,ans[N],c[N],s[N],v[N];
int f[2][N],inv[M];

inline bool cmp(node a,node b){return a.a<b.a;}

inline void update(int &x,int y){
x=1ll*(x+y)%Mod;
}

inline void killer_queen_bites_the_dust(int x){
int p1=1ll*c[x]*inv[s[x]]%Mod,p2=1ll*(c[x]-s[x])*inv[c[x]]%Mod;
if(p1) for(int i=n-1;i>=0;i--) f[0][i]=1ll*f[1][i+1]*p1%Mod,f[1][i]=(f[1][i]-1ll*f[0][i]*p2%Mod+Mod)%Mod;
else for(int i=n-1;i>=0;i--) f[0][i]=f[1][i];
}

inline void up(int x){
int p1=1ll*s[x]*inv[c[x]]%Mod,p2=1ll*(c[x]-s[x])*inv[c[x]]%Mod;
for(int i=0;i<=n;i++) f[1][i]=(1ll*(i?f[0][i-1]:0)*p1%Mod+1ll*f[0][i]*p2%Mod)%Mod;
}

signed main(){
n=read();inv[1]=1;
for(int i=2;i<M;i++) inv[i]=(Mod-1ll*Mod/i*inv[Mod%i]%Mod)%Mod;
for(int i=1;i<=n;i++){
int k=read();
while(k--){b[++m]=(node){read(),100-read(),read(),i};c[i]+=b[m].p;}
}
for(int i=1;i<=n;i++) v[i]=read();
sort(b+1,b+m+1,cmp);f[1][0]=1;
for(int i=1;i<=m;i++){
killer_queen_bites_the_dust(b[i].id);
for(int j=0;j<n;j++)
update(ans[b[i].id],1ll*v[n-j]*b[i].g%Mod*inv[100]%Mod*f[0][j]%Mod*b[i].p%Mod*inv[c[b[i].id]]%Mod);
s[b[i].id]+=b[i].p;
up(b[i].id);
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
感谢您又打赏