CodeForces-1279D Santa's Bot（逆元）

传送门：CodeForces - 1279D

题目描述

Santa Claus has received letters from n different kids throughout this year. Of course, each kid wants to get some presents from Santa: in particular, the i-th kid asked Santa to give them one of ki different items as a present. Some items could have been asked by multiple kids.

Santa is really busy, so he wants the New Year Bot to choose the presents for all children. Unfortunately, the Bot’s algorithm of choosing presents is bugged. To choose a present for some kid, the Bot does the following:

• choose one kid x equiprobably among all n kids;
• choose some item y equiprobably among all kx items kid x wants;
• choose a kid z who will receive the present equipropably among all n kids （this choice is independent of choosing x and y）; the resulting triple (x,y,z) is called the decision of the Bot.

If kid z listed item y as an item they want to receive, then the decision valid. Otherwise, the Bot’s choice is invalid.

Santa is aware of the bug, but he can’t estimate if this bug is really severe. To do so, he wants to know the probability that one decision generated according to the aforementioned algorithm is valid. Can you help him?

输入描述

The first line contains one integer n $(1≤n≤10^6)$ — the number of kids who wrote their letters to Santa.

Then n lines follow, the i-th of them contains $a$ list of items wanted by the i-th kid in the following format: $k_i a_{i,1} a_{i,2} … a_{i,k_i}$ $(1≤k_i,a_i,j≤10^6)$, where $k_i$ is the number of items wanted by the i-th kid, and $a_{i,j} are the items themselves. No item is contained in the same list more than once.

It is guaranteed that $\sum_{i=1}^{n}{k_i}<=10^6$.

输出描述

Print the probatility that the Bot produces a valid decision as follows:

Let this probability be represented as an irreducible fraction $xy$. You have to print $x⋅y^{-1}$ mod 998244353, where $y^{-1}$ is the inverse element of $y$ modulo 998244353 （such integer that $y⋅y^{-1}$ has remainder 1 mod 998244353）.

思路分析

总共有n个人，每一个人喜欢ki种不同的东西,n个人里面抽一个是 $\frac{1}{n}$
从n个人里面抽一个，然后从这个人喜欢的东西里面抽一个,从$k_i$个东西里面抽是$\frac{1}{k_i}$
然后任意在所有人里面抽一个，问这个人喜欢的礼物和之前的那个喜欢的东西重复的概率.最后从n个人里面抽一个的正好重复的概率是$\frac{想要这个礼物的人数}{n}$

最后乘起来就是总概率了。

这道题需要用到乘法逆元，具体怎么算可以去看这个网站 OI Wiki 乘法逆元

样例输入

2
2 2 1
1 1

样例输出

124780545

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>


using namespace std;

#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;
const int mod=998244353;

inline int read () {
    register int s = 0, w = 1;
    register char ch = getchar ();
    while (! isdigit (ch)) {if (ch == '-') w = -1; ch = getchar ();}
    while (isdigit (ch)) {s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar ();}
    return s * w;
}
const int N=1e6+10;

ll q(ll a,ll b){
    ll sum=1;
    while(b){
        if(b&1)sum=sum%mod*a%mod;
        a=(ll)a*a%mod;
        b>>=1;
    }
    return sum%mod;
}
ll inv(ll a,ll b){
    return (a%mod*q(b,mod-2)%mod)%mod;
}

ll b[N];
vector<ll>a[N];

int main() {
    
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        ll n;
        cin>>n;
        for(int j=0;j<n;j++){
            ll x;
            cin>>x;
            a[i].push_back(x);
            b[x]++;
        }
    }
    ll ans=0;
    for(int i=0;i<t;i++)
        for(int j=0;j<a[i].size();j++)
            ans=ans%mod+(inv(1,t)%mod*inv(1,a[i].size())%mod*inv(b[a[i][j]],t))%mod;
        
    cout<<ans%mod<<endl;
    return 0;
}