Educational Codeforces Round 79 (Rated for Div. 2)

题意：有$n$个孩子，第$i$个孩子有$k[i]$件想要的礼物，第$j$个礼物为$a[i][j]$，现在随机挑一个孩子，从他想要的礼物里面随机挑一个，然后送给另一个孩子$($这个孩子可以和第一个孩子是同一个人$)$，问你送的这个礼物在后一个孩子愿望单里的概率。

思路：求出每件礼物出现的次数$cnt[]$，挑出第一个孩子的概率为$\frac{1}{n}$，在他的愿望单里挑出一件礼物的概率为$\frac{1}{k[i]}$，挑出另一个孩子的概率也是$\frac{1}{n}$，挑出的第一个孩子的每件礼物$a[i][j]$出现了$cnt[a[i][j]]$次，那么对于第$i$个孩子的第$j$件礼物$a[i][j]$礼物而言，对答案的贡献就是$\frac{cnt[a[i][j]]}{n^{2}*k[i]}$，所以总概率$$p=\sum_{i=1}^{n}\sum_{j=1}^{k[i]}\frac{cnt[a[i][j]]}{n^{2}*k[i]}$$用快速幂取逆元。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long ll;

const int N = ;

const ll mod = ;

ll n, k[N], s[N], cnt[N];

vector<ll> v[N];

ll power(ll a, ll n, ll p)

{

    ll ba = a, res = ;

    while (n) {

        if ( == n % ) res = (res * a) % p;

        a = (a * a) % p, n /= ;

    }

    return res;

}

int main()

{

    scanf("%lld", &n);

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

        scanf("%lld", &k[i]);

        for (int j = ; j <= k[i]; j++) {

            ll a;

            scanf("%lld", &a);

            cnt[a]++, v[i].push_back(a);

        }

    }

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

        for (int j = ; j < k[i]; j++) s[i] += cnt[v[i][j]];

    }

    ll res = ;

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

        ll tp = ((n * n) % mod * k[i] % mod) % mod;

        ll inv = power(tp, mod - , mod);

        res = (res + (s[i] * inv) % mod) % mod;

    }

    printf("%lld\n", res);

    return ;

}

巴特西

Educational Codeforces Round 79 (Rated for Div. 2) - D. Santa's Bot(数论)

最新文章

热门文章