萌新80分求助
查看原帖
萌新80分求助
748394
wyb__Dad楼主2024/5/14 16:56
#include<bits/stdc++.h>
using namespace std;
long long int n,m,c[1000010][7],rs[1000010],cs[1000010],t;
long long int dl[1000010];
__int128 fz[1000010],fm[1000010];
void asd(int y){
	__int128 a=fz[y],b=fm[y];
	while(a!=0){
		__int128 z=b;
		b=a;
		a=z-a*int(z/a);
	}
	fz[y]=fz[y]/b;
	fm[y]=fm[y]/b; 
}
void sc(__int128 x){
	if(x>9)
	sc(x/10);
	putchar(x%10+'0');
	return;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		for(int j=1;j<=x;++j){
			int y;
			cin>>y;
			rs[y]++;
			cs[i]++;
			c[i][cs[i]]=y;
			
		}
	}
	for(int i=1;i<=n;++i){
		if(rs[i]==0){
			t++;
			dl[t]=i;
		}
	}
	for(int i=1;i<=n;++i){
		fm[i]=1;
	}
	int x=1;
	while(t<n){
		for(int i=1;i<=cs[x];++i){
			rs[c[x][i]]-=1;
			if(rs[c[x][i]]==0){
				t+=1;
				dl[t]=c[x][i];
			}
		}
		x+=1;
	}
	for(int i=1;i<=m;++i){
		fz[dl[i]]=1;
	}
	for(int i=1;i<=n;++i){
		int x=dl[i];
		for(int j=1;j<=cs[x];++j){
			int y=c[x][j];
			__int128 z=fm[x]*cs[x];
			fz[y]=fz[y]*z+fz[x]*fm[y];
			fm[y]=z*fm[y];
			asd(y);
		}
	} 
	for(int i=1;i<=n;++i){
		if(cs[i]==0){
			sc(fz[i]);
			cout<<" ";
			sc(fm[i]);
			cout<<endl;
		}
	}
	return 0;
}
2024/5/14 16:56
加载中...