思路
做法一：组合数学
操作分三步，前两步选孩子再选礼物，最后一步再选孩子。
因此求出两步内选到礼物i的概率，再乘上想要礼物i的孩子的占比，求和所有礼物的结果就是答案。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define maxn 2000000
#define M 998244353
set<int> gi;
ll sum[maxn];
int cnt[maxn];
ll qpow(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % M;
a = (a * a) % M;
b = b >> 1;
}
return res;
}
ll ddiv(ll a, ll b) { // a/b
return a * qpow(b, M - 2) % M;
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
ll tmp = ddiv(1, n);
for(int i = 1; i <= n; i++) {
int k;
cin >> k;
ll ttmp = ddiv(1, k);
for(int i = 0; i < k; i++) {
int g;
cin >> g;
gi.insert(g);
sum[g] = (sum[g] + (tmp * ttmp % M)) % M;
cnt[g]++;
}
}
ll ans = 0;
for(auto g : gi) {
ans = (ans + (sum[g] * ddiv(cnt[g], n)) % M) % M;
}
cout << ans ;
}
做法二：dp
dp[i]代表选了第i个孩子的概率。然后有四种情况分类讨论，详情见代码。
注意，对于这个解法，用了太多次的快速幂会超时，因此要保存一些快速幂的结果减少计算量。
显然，做法一更好
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define maxn 2000000
#define M 998244353
ll dp[maxn];
vector<int> ch[maxn];
vector<int> gi[maxn];
ll sum[maxn];
ll qpow(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % M;
a = (a * a) % M;
b = b >> 1;
}
return res;
}
ll ddiv(ll a, ll b) { // a/b
return a * qpow(b, M - 2) % M;
}
inline ll pow2(ll a) {
return (a * a) % M;
}
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
int k;
cin >> k;
while(k--) {
int g;
cin >> g;
ch[i].push_back(g);
}
}
dp[0] = 1;
for(int i = 1; i <= n; i++) {
ll a = pow2(ddiv(i - 1, i)) * dp[i - 1] % M ;
ll b = pow2(ddiv(1, i));
ll c = 0;
ll d = 0;
for(int g : ch[i]) {
c = (c + ddiv(1, ch[i].size()) * ddiv(gi[g].size(), i - 1) % M) % M;
d = (d + (ddiv(1, i - 1) * sum[g]) % M) % M;
}
for(int g : ch[i]) {
gi[g].push_back(i);
if(sum[g] == 0) sum[g] = ddiv(1, ch[i].size());
else sum[g] = (sum[g] + ddiv(1, ch[i].size())) % M;
}
ll tmp = (ddiv(1, i) * ddiv(i - 1, i) % M);
d = tmp * d % M;
c = tmp * c % M;
dp[i] = (a + b + c + d) % M;
}
cout << dp[n];
}