51nod 抽卡大赛

抽卡大赛

链接

分析：

　　$O(n^4)$的做法比较好想，枚举第i个人选第j个，然后背包一下，求出有k个比他大的概率。

　　优化：

　　第i个人，选择一张卡片，第j个人选的卡片大于第i个人的概率是$p_j$，那么答案的生成函数是：

　　$\prod \limits _{j = 1}^{n} [j != i]((1 - p_j) + p_jx)$

　　那么可以将所有人选的卡片按A排序，每次移动，只有一个多项式发生改变，改变的只有一个人，每个人只有一个长度为2的多项式，乘和除都可以做到$O(n)$。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cctype>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<bitset>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = 1e9 + , inv100 = ;

struct Node { int A, G, P, id; } a[N * N];

bool operator < (const Node& x,const Node &y) { return x.A > y.A; }

int f[N], v[N], sump[N], ans[N], n;

int ksm(int a,int b) {

    int res = ;

    while (b) {

        if (b & ) res = 1ll * res * a % mod;

        a = 1ll * a * a % mod;

        b >>= ;

    }

    return res;

}

void Div(int p) {

    int inv = ksm( - p, mod - );

    f[] = 1ll * f[] * inv % mod;

    for (int i = ; i < n; ++i) f[i] = 1ll * (f[i] - 1ll * p * f[i - ] % mod) * inv % mod;

}

void Mul(int p) {

    for (int i = n - ; i >= ; --i)

    f[i] = (1ll * f[i] * (mod +  - p) % mod + 1ll * f[i - ] * p % mod) % mod;

}

int main() {

    n = read();int cnt = ;

    for (int i = ; i <= n; ++i) {

        int m = read(), sum = ;

        for (int j = ; j <= m; ++j) {

            a[++cnt].id = i;

            a[cnt].A = read(), a[cnt].G = read(), a[cnt].P = read(); sum += a[cnt].P;

            a[cnt].G = 1ll * ( - a[cnt].G) * inv100 % mod;

        }

        for (int j = ; j < m; ++j)

            a[cnt - j].P = 1ll * a[cnt - j].P * ksm(sum, mod - ) % mod;

    }

    for (int i = ; i < n; ++i) v[i] = read();

    sort(a + , a + cnt + );

    f[] = ;

    for (int i = ; i <= cnt; ++i) {

        if (a[i].id != a[i - ].id) {

            Div(sump[a[i].id]);

            Mul(sump[a[i - ].id]);

        }

        for (int j = ; j < n; ++j)

            ans[a[i].id] = (ans[a[i].id] + 1ll * f[j] * v[j] % mod * a[i].P % mod * a[i].G) % mod;

        sump[a[i].id] = (sump[a[i].id] + a[i].P) % mod;

    }

    for (int i = ; i <= n; ++i) printf("%d\n", (ans[i] + mod) % mod);

    return ;

}