51nod 1850 抽卡大赛（动态DP？雾）

51Nod为了活跃比赛前的气氛，组织了场抽卡比赛。这场比赛共 n个人参加，主办方根据非欧血统鉴定器，得到了一些数据。每个人抽卡有 Mi 种可能，得到的卡能力值为 Aij 代价为 Gij 的可能性为 Pij ，所谓代价指的是玩家需要将一轮比赛后所得的点头盾的 Gij% 交给主办方。每轮比赛每个人都随机抽取卡片，待全部人抽取完毕后进行排名（按照A从大到小排），排在第 i 位的人有 Vi 的点头盾收入。现在主办方想知道一轮比赛后每个人的期望收入。

第一行一个正整数 n

接下来 n 个部分

每个部分第一行为正整数 Mi，接下来 Mi 行有三个整数 Aij Gij Pij

接下来一行 n 个整数，分别为 Vi

设 ∑Pij=Qi，则第 i 个人抽到第 j 张卡的概率为 Pij/Qi

1<=n,Mi<=200，1<=Aij<=1000000000，保证 Aij 互不相同，0<=Gij<=100，1<=Pij<=1000，1<=Vi<=1000

容易想到算枚举人，枚举他抽的哪张卡，求是第k名的概率。

暴力dp是 O ( n 4 ) O(n^4) O(n4)的。

发现重复计算很多。

从小到大枚举卡的权值，求这个权值是第k名的概率 a k a_k ak​。

那么我们可以转而求它的生成函数： F ( x ) = ∑ i = 0 n a i x i F(x) = \sum_{i=0}^n a_i x^i F(x)=∑i=0n​ai​xi

可以发现当我们枚举的权值为 v a l val val时。

F ( x ) = ∏ i = 1 n ( p i x + ( 1 − p i ) ) F(x) = \prod_{i=1}^n(p_ix+(1-p_i)) F(x)=∏i=1n​(pi​x+(1−pi​))

p i p_i pi​为第i个人抽的卡的值 &gt; v a l &gt;val >val的几率。

然后发现在 v a l val val增大时，我们只会改变乘积式中的一个一次多项式。

一次多项式除法+多项式乘法即可。

注意到这里的第二个多项式是一次的。

可以 O ( n ) O(n) O(n)(就是做dp)

求出这个生成函数之后，再除一下那个人的多项式就可以统计那个人那个权值的答案。

O ( n 3 ) O(n^3) O(n3)

具体看代码。

AC Code:

#include<bits/stdc++.h>
#define maxn 405
#define mod 1000000007
using namespace std;

int n,m[maxn],a[maxn][maxn],g[maxn][maxn],p[maxn][maxn],ps[maxn],pns[maxn],val[maxn];
int pol[maxn],inv[400005]={1,1},tmp[maxn];
int ans[maxn];

struct node{
	int x,y;
	bool operator <(const node &B)const{ return a[x][y] > a[B.x][B.y]; }
}Q[maxn*maxn];
int cnt = 0;

int Pow(int base,int k){
	int ret = 1;
	for(;k;k>>=1,base=1ll*base*base%mod)
		if(k&1)
			ret=1ll*ret*base%mod;
	return ret;
}

void Div(int p){
	if(p){
		int p1 = 1 - p , ivp = Pow(p,mod-2);
		for(int i=n;i>=0;i--) 
			tmp[i] = (pol[i+1] - 1ll * tmp[i+1] * p1) % mod * ivp % mod;
		for(int i=0;i<=n;i++) 
			pol[i] = tmp[i];
	}
}

void Mul(int p){
	int p1 = 1 - p;
	for(int i=0;i<=n;i++)
		tmp[i] = (1ll * pol[i] * p1 + (i ? 1ll * p * pol[i-1] : 0)) % mod;
	for(int i=0;i<=n;i++) pol[i] = tmp[i];
}

int main(){
	scanf("%d",&n);
	pol[0] = 1;
	for(int i=1;i<=n;i++){
		scanf("%d",&m[i]);
		for(int j=1;j<=m[i];j++){
			scanf("%d%d%d",&a[i][j],&g[i][j],&p[i][j]);
			ps[i] += p[i][j];
			Q[++cnt].x = i , Q[cnt] . y = j;
		}
	}
	for(int i=2;i<=300000;i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	for(int i=0;i<n;i++) scanf("%d",&val[i]);
	sort(Q+1,Q+1+cnt);
	for(int i=1;i<=cnt;i++){
		//for(int j=0;j<n;j++) 
		//	printf("pol[%d] = %d\n",j,pol[j]);
		//printf("%lld\n",1ll * pns[Q[i].x] * inv[ps[Q[i].x]] % mod);
		Div(1ll * pns[Q[i].x] * inv[ps[Q[i].x]] % mod);
		//for(int j=0;j<n;j++) 
		//	printf("pol[%d] = %d\n",j,pol[j]);
		//printf("@%d %d %d\n",Q[i].x,Q[i].y,a[Q[i].x][Q[i].y]);
		for(int j=0;j<n;j++)
		{
			//printf("%d %d %d\n",(pol[j]+mod)%mod,val[j],g[Q[i].x][Q[i].y]);
			ans[Q[i].x] = (ans[Q[i].x] + 1ll * pol[j] * val[j] % mod * 
				p[Q[i].x][Q[i].y] % mod * 
				inv[ps[Q[i].x]] % mod * (100-g[Q[i].x][Q[i].y]) % mod * inv[100]) % mod;
			//printf("%d\n",ans[Q[i].x]);
		}
		pns[Q[i].x] += p[Q[i].x][Q[i].y];
		Mul(1ll * pns[Q[i].x] * inv[ps[Q[i].x]] % mod);
		//for(int j=0;j<n;j++) 
		//	printf("pol[%d] = %d\n",j,pol[j]);
	}
	for(int i=1;i<=n;i++)
		printf("%d\n",(ans[i]+mod)%mod);
}