【题解】抽卡大赛 概率 dp+优化 trick 51nod1850 ——quhengyi11

传送门

老年鸽子选手过来暖站

题意就是求抽卡排名分布

题解

首先考虑暴力

我们枚举每个人抽到的卡，然后去用概率 dp 算出这个人排名为 $x$的概率

具体来讲，我们设 $f_{x,y}$表示前 $x$个人 (不包括它自己)，有 $y$个人比它弱的概率

得到方程

$$f_{x,y}=p_xf_{x-1,y-1}+(1-p_x)f_{x-1,y-1}$$

其中 $p_x$表示这个人胜过第 $x$人的概率，公式化来讲，设当前这个人拿的卡的能力值为 $A$，那么

$$p_x=(\sum_{a_{x,i} < A} p_{x,i})/sum_x$$

其中 $a_{x,i},p_{x,i}$如题意所示，$sum_x=\sum p_{x,i}$

这个算法枚举卡片为 $O(n^2)$，算方程为 $O(n^2)$，总复杂度为 $O(n^4)$

我们发现这个算法的瓶颈在于枚举每个人的每张卡片的时候，每次的 $p_i$都要被重新算一遍，这样枚举就 $O(n^2)$了。

所以我们有一个很妙的搞法，我们将所有卡片按照能力值来从小到大排序，然后按顺序计算它们对答案的贡献。

因为我们是按能力值从小到大处理的，所以我们每次枚举 $p_x$只会变化一个，所以改变 $p_x$是 $O(1)$的复杂度，但是我们又发现一个问题，原来算法的 $dp$是不包括当前枚举的那个人计算出的结果，我们这里又怎么做呢？

经过观察我们发现，我们设 $g_x$表示当前有 $x$人比自己弱，设 $f_x$表示除去当前枚举的这个人 $i$之后有 $x$个人比自己弱

类似上面的式子，我们可以知道

$$g_x=f_{x-1}p_i+f_x(1-p_i)$$

我们发现这个式子变一变可以由 $g$逆推到 $f$，即

$$f_{x}=\frac{g_x-p_if_{x-1}}{1-p_i}$$

然后我们就可以每次用 $O(n)$的时间将 $f$给算出来，然后再更新答案和更新 $g$，所以总复杂度是 $O(n^3)$的

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define N 200005
struct node {
    int id;
    ll a, g, p;
    friend bool operator < (node x, node y) { return x.a < y.a; }
} q[N];
int t, n, m;
ll inv[N], ans[N], f[N], g[N], now[N], sum[N], v[N];
inline void ins (int x)
{
    ll pi = now[x] * inv[sum[x]] % mod, api = (1 - pi + mod) % mod;
    fo (x, 0, n - 1) g[x] = (f[x - 1] * pi + f[x] * api) % mod;
}
inline void del (int x)
{
    ll pi = now[x] * inv[sum[x]] % mod, invapi = inv[sum[x] - now[x]] * sum[x] % mod;
    f[0] = g[0] * invapi % mod;
    fo (x, 1, n - 1) f[x] = (g[x] - f[x - 1] * pi % mod + mod) * invapi % mod;
}
int main ()
{
    inv[1] = 1;
    fo (i, 2, 2e5) inv[i] = mod - mod / i * inv[mod % i] % mod;
    scanf("%d", &n);
    fo (i, 1, n)
    {
        scanf("%d", &m);
        while (m--) 
        {
            ++t;
            scanf("%lld %lld %lld", &q[t].a, &q[t].g, &q[t].p);
            sum[i] += q[t].p;
            q[t].id = i;
            q[t].g = (100 - q[t].g) * inv[100] % mod;
        }
    }
    std::sort(q + 1, q + t + 1);
    fo (i, 1, n) scanf("%lld", &v[i]);
    g[0] = 1;
    fo (i, 1, t)
    {
        del(q[i].id);
        fo (x, 0, n - 1)
            (ans[q[i].id] += f[x] * v[n - x] % mod * q[i].g % mod * q[i].p % mod * inv[sum[q[i].id]]) %= mod;
        now[q[i].id] += q[i].p;
        ins(q[i].id);
    }
    fo (i, 1, n) printf("%lld\n", ans[i]);
    return 0;
}