51nod

分析

首先考虑一个暴力做法。

假设我们现在正在计算张三的期望收益。则根据期望的线性性，我们只需要求出张三抽到某一张卡时位于某一个排名的概率。

枚举张三抽到的卡（为了方便称这张卡为 A），然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个不是张三的人中有 $j$ 个抽到的卡比张三大的概率。设 $p$ 为第 $x$ 个不是张三的人抽到的卡比 A 大的概率，容易得到转移

$$
dp_{i,j}=p\times dp_{i-1,j-1}+(1-p)\times dp_{i-1,j}
$$

这样子是 $\mathcal{O}(n^4)$ 的，显然过不了。考虑一些优化。

假设张三抽到了卡 A，设 $a_i$ 为张三的排名为 $i$ 的概率，考虑求出 $\{a_i\}$ 的生成函数 $F(x)$。

设 $p_i$ 为第 $i$ 个人抽的卡比 A 大的概率，则

$$
F(x)=\prod_{i\neq x}(p_ix+1-p_i)
$$

现在的问题是如何快速求出每个人的每张卡对应的 $F(x)$。考虑将所有人的所有卡从大到小排序，并维护生成函数

$$
G(x)=\prod_{i=1}^n(p'_ix+1-p'_i)
$$

这里的 $p'_i$ 为第 $i$ 个人抽的卡大于当前枚举的卡的概率。

那么我们只需要将 $G(x)$ 除以一个二项式即可得到 $F(x)$，然后当枚举的卡改变时 $G(x)$ 只会除以一个二项式再乘一个二项式，可以在 $\mathcal{O}(n)$ 的时间内维护。总时间复杂度降为 $\mathcal{O}(n^3)$，可以通过此题。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}
const int inv100=qpow(100,mod-2);
const int N=200+10;

int n,cnt=0;
int a[N][N],g[N][N],p[N][N],v[N],invp[N],sp[N],ans[N];
struct card { int p,id; } c[N*N];
bool operator <(card x,card y) { return a[x.p][x.id]>a[y.p][y.id]; }

int F[N];
void mul(int p) { int q=(1-p+mod)%mod;
    for (int i=n;i;--i) F[i]=(1ll*F[i-1]*p+1ll*F[i]*q)%mod;
    F[0]=1ll*F[0]*q%mod;
}
void div(int p) { int invq=qpow((1-p+mod)%mod,mod-2);
    F[0]=1ll*F[0]*invq%mod;
    for (int i=1;i<=n;++i) F[i]=(F[i]-1ll*F[i-1]*p%mod+mod)*invq%mod;
}   

int main() {
    n=read();
    for (int i=1;i<=n;++i) {
        int m=read();
        for (int j=1;j<=m;++j) {
            a[i][j]=read(),g[i][j]=read(),p[i][j]=read();
            g[i][j]=(1-1ll*g[i][j]*inv100%mod+mod)%mod,invp[i]+=p[i][j];
            c[++cnt]=(card){i,j};
        }
        invp[i]=qpow(invp[i],mod-2);
    }
    for (int i=0;i<n;++i) v[i]=read();
    sort(c+1,c+cnt+1); F[0]=1;
    for (int i=1;i<=cnt;++i) {
        div(1ll*sp[c[i].p]*invp[c[i].p]%mod);
        for (int j=0;j<n;++j) {
            int P=1ll*p[c[i].p][c[i].id]*invp[c[i].p]%mod;
            int W=1ll*F[j]*v[j]%mod*g[c[i].p][c[i].id]%mod;
            ans[c[i].p]=(ans[c[i].p]+1ll*P*W)%mod;
        }
        sp[c[i].p]+=p[c[i].p][c[i].id];
        mul(1ll*sp[c[i].p]*invp[c[i].p]%mod);
    }
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}