oitiku90分,怎么luogu爆零
查看原帖
oitiku90分,怎么luogu爆零
3827
syther楼主2020/12/6 15:48
#include <bits/stdc++.h>
using namespace std;


int gcd(int a,int b)
{
	if(b == 0)	return a;
	return gcd(b,a%b);
}
struct node{
	int fenmu;
	int fenzi;
	node()
	{
		fenmu = 1;
		fenzi = 0;
	};
};
node hj(node a)
{
	int gys = gcd(a.fenzi,a.fenmu);
	a.fenzi /= gys;
	a.fenmu /= gys;
	return a;
}
node d(node a,int b)
{
	a.fenmu *= b;
	
	return hj(a);
}
node add(node a,node b)
{
	int gys = gcd(a.fenmu,b.fenmu);
	node res;
	res.fenmu = a.fenmu / gys * b.fenmu;
	res.fenzi = a.fenzi * (b.fenmu / gys) + b.fenzi * (a.fenmu / gys);
	return hj(res);
}




int n,m;
vector<int> g[100001];
node v[100001];
vector<int> o;

int main()
{
	ios::sync_with_stdio(false);
	//freopen("water.in","r",stdin);
	//freopen("water.out","w",stdout);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		int d;cin >> d;
		for(int j = 1; j <= d; j++)
		{
			int a;cin >> a;
			g[i].push_back(a);
		}
		if(d == 0) o.push_back(i);
	}
	
	for(int i = 1; i <= n; i++)
	{
		
		
		if(i <= m ) v[i].fenzi += v[i].fenmu;
		node val = v[i];
		if(g[i].size() == 0)	continue;
		val = d(val,g[i].size());
		for(int j = 0; j < g[i].size(); j++)
		{
			int k = g[i][j];
			//i 鎺ュ彈鍙g紪鍙?
			//k 杈撳嚭鍙g紪鍙?
			v[k] = add(val,v[k]);
		}
	}
	
	for(int i = 0; i < o.size(); i++)
	{
		cout << v[o[i]].fenzi <<" "<< v[o[i]].fenmu << endl;
	}
	return 0;
}
2020/12/6 15:48
加载中...