Quiz

ちょうどいい問題があった D. Santa's Bot
https://codeforces.com/contest/1279/problem/D

AC

https://codeforces.com/contest/1279/submission/69267347

modintの借り先

snukeさんのmint
https://github.com/atcoder-live/library/blob/master/mint.cpp

例題 sample-1

2
2 2 1
1 1

1/2の確率で人1を選び、その上で2が選ばれる確率は1/2, 1が選ばれる確率も1/2
1/2の確率で人2を選び、その上で1が選ばれる確率が1
よって
- yとして1が選ばれる確率は1/4 + 1/2 = 3/4
- yとして2が選ばれる確率は1/4
validな確率を考える
1/2で人1が選ばれ、y=1 or 2であればvalid。確率は1/2 x 1
1/2で人2が選ばれ、y=1であればvalid。確率は1/2 x 3/4
よってvalidになる確率の合計は1/2 + 3/8 = 7/8
（ここまでは正しく求められていたか確認しよう。そうでない場合、問題が読めていない可能性）
7/8は、modで表現すると124780545になるので、サンプルが合う

Code (main)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin >> N;

    // sample-1
    // mint a = 7;
    // a /= 8;
    // p(a.x); return 0;

    VV G(N);
    vector<mint> P(1000010);
    ll all = 0;

    rep(i, N){
      ll k;cin>>k;
      all += k;
      rep(j, k){
        ll p;cin>>p;
        G[i].push_back(p);
      }
    }

    // yの出現確率
    rep(i, N){
      ll sz = SZ(G[i]);
      for(ll a : G[i]){
        mint m = 1;
        m /= N;
        m /= sz;
        P[a] += m;
      }
    }

    mint ans = 0;
    rep(i, N){
      for(ll a : G[i]){
        ans += P[a];        
      }
    }
    ans /= N;
    p(ans.x);

    return 0;
}