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);
}