1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <bits/stdc++.h> #define pb push_back using I128 = __int128; using namespace std; const int N = 1e5 + 100; int n, m; I128 gcd(I128 x, I128 y){ return (!y) ? (x) : (gcd(y, x % y)); } struct Fen { I128 p, q; Fen operator + (Fen y) { I128 _p = p * y.q + y.p * q, _q = q * y.q; I128 d = gcd(_p, _q); _p /= d, _q /= d; return {_p, _q}; } Fen operator / (I128 y) { I128 d = gcd(y, p); I128 _p = p / d; y /= d; I128 _q = q * y; return {_p, _q}; } } a[N]; std::vector<int> to[N]; std::queue<int> q; int du[N]; void wt(I128 x) { if (x < 0) putchar('-'), x = -x; if (x > 9) wt(x / 10); putchar(x % 10 + 48); } int main() { scanf("%d %d", &n, &m); for (int i = 1, d; i <= n; ++i) { scanf("%d", &d); for (int j = 1, t; j <= d; ++j) { scanf("%d", &t); to[i].pb(t), ++du[t]; } } for (int i = 1; i <= n; ++i) a[i] = {0, 1}; for (int i = 1; i <= m; ++i) a[i] = {1, 1}, q.push(i); while (!q.empty()) { int x = q.front(); q.pop(); if (!to[x].size()) continue; a[x] = a[x] / to[x].size(); for (int y : to[x]) { a[y] = a[y] + a[x]; if (!(--du[y])) q.push(y); } } for (int i = 1; i <= n; ++i) if (!to[i].size()) wt(a[i].p), putchar(' '), wt(a[i].q), putchar('\n'); return 0; }
|