最后两个过不了,确保程序思路无问题,只是 __int128
方面的问题,求助。
#include<bits/stdc++.h>
using namespace std;
#define int unsigned __int128
inline int read(){
int x=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
void print(int x){
if(!x)return;
if(x)print(x/10);
putchar(x%10+'0');
}
int n,m,num,in[100005];
vector<int>e[100005];
int ans[100005],tmp;
struct node{
int a,b;
}t[100005];
void topo(){
queue<int>q;
for(int i=1;i<=n;++i){
if(!in[i]){
q.push(i);
t[i].a=1,t[i].b=1;
}
}
while(!q.empty()){
int u=q.front();
ans[++tmp]=u;
q.pop();
for(int i=0;i<e[u].size();++i){
int v=e[u][i];
in[v]--;
if(!in[v])q.push(v);
}
}
}
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
node add(int a,int b,int c,int d){
node q;
int lcm=b*d/gcd(b,d);
a*=lcm/b,c*=lcm/d;
q.a=a+c,q.b=lcm;
int gcdd=gcd(q.a,q.b);
q.a/=gcdd,q.b/=gcdd;
return q;
}
node mul(int a,int b,int c,int d){
node q;
q.a=a*c,q.b=b*d;
int gcdd=gcd(q.a,q.b);
q.a/=gcdd,q.b/=gcdd;
return q;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
num=read();
int v;
for(int j=1;j<=num;++j){
v=read();
e[i].push_back(v);
in[v]++;
}
}
topo();
for(int i=1;i<=n;++i){
if(!e[i].size())print(t[i].a),printf(" "),print(t[i].b),puts("");
node ans=mul(t[i].a,t[i].b,1,e[i].size());
for(int j=0;j<e[i].size();++j){
int v=e[i][j];
if(!t[v].a&&!t[v].b)t[v]=ans;
else t[v]=add(t[v].a,t[v].b,ans.a,ans.b);
}
}
return 0;
}