CodeForces 1279D - Santa's Bot 题解

现在看来当时是真的菜，不过还是能学到一些奇怪的知识 233

题解 #

最多有 $10^6$ 对 $(x,y)$ ，所以我们可以直接遍历所有的对。每一对有 $\dfrac 1 {n\cdot k_x}$ 的概率被选中，所以一个合法的 $(x,y,z)$ 的概率是 $\dfrac {cnt_y} {n\cdot k_x\cdot n}$ ，其中 $cnt_y$ 是想要 y 礼物的孩子的个数。

一个有意思的性质是 $\dfrac a b +\dfrac c d\equiv ab^{-1}+cd^{-1}\pmod p$ ，当 $p$ 与分母互质的时候成立，所以我们在遍历的时候可以直接把概率转换成 $cnt_y\cdot n^{-1}\cdot k_x^{-1}\cdot n^{-1}$ 然后加到答案上。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int p=998244353;
const int N=1e6+5;
vector<int> a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n;
    cin>>n;
    ll ans=0;
    map<int,int> cnt;
    vector<ll> inv(N+1);
    inv[1]=1;
    for(int i=2;i<=N;i++) inv[i]=ll(p-p/i)*inv[p%i]%p;
    forn(i,n){
        int k;
        cin>>k;
        a[i].resize(k);
        for(auto& it:a[i]){
            cin>>it;
            cnt[it]++;
        }
    }
    forn(i,n){
        for(auto it:a[i]){
            ll x=cnt[it]*inv[n]%p*inv[n]%p*inv[size(a[i])]%p;
            ans=(ans+x)%p;
        }
    }
    cout<<ans;
    return 0;
}