显然我们可以发现答案是每个可以互相到达的集合的大小取排列然后依次相乘起来。考虑如何找到每一个互补相不的集合，即hash。(然而我取了3模数才过)
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1000010 10 #define md (llg)(1000100000001007) 11 #define MD 1000000007 12 #define md2 (llg)(5456145545456) 13 #define md3 (llg)(100007) 14 #define llg long long 15 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 16 llg n,m,a[maxn],p[maxn],l,r; 17 18 struct node 19 { 20 llg a1,a2,a3; 21 }c[maxn]; 22 23 bool cmp(const node&a,const node&b) 24 { 25 if (a.a1==b.a1 && a.a2==b.a2) return a.a3<b.a3; 26 if (a.a1==b.a1) return a.a2<b.a2; 27 return a.a1<b.a1; 28 } 29 30 int main() 31 { 32 srand(1346); 33 // yyj("C"); 34 p[0]=p[1]=1; 35 for (llg i=2;i<=1000000;i++) p[i]=p[i-1]*i,p[i]%=MD; 36 cin>>n>>m; 37 llg inc=1; 38 for (llg k=1;k<=n;k++) 39 { 40 llg x; 41 inc=rand()%md+1; llg inc2=rand()%md+1,inc3=rand()%md+1; 42 scanf("%I64d",&x); 43 for (llg i=1;i<=x;i++) 44 { 45 scanf("%I64d",&a[i]); 46 c[a[i]].a1+=inc; c[a[i]].a2+=inc2; c[a[i]].a3+=inc3; 47 c[a[i]].a1%=md; c[a[i]].a2%=md2; c[a[i]].a3%=md3; 48 } 49 inc*=2; 50 inc%=md; 51 } 52 llg ans=1; 53 sort(c+1,c+m+1,cmp); 54 l=1; 55 while (l<=m) 56 { 57 r=l; 58 while (c[r+1].a1==c[l].a1 && c[r+1].a2==c[l].a2 && c[r+1].a3==c[l].a3 && r+1<=m) r++; 59 ans*=p[r-l+1]; 60 ans%=MD; 61 l=r+1; 62 } 63 // for (llg i=1;i<=c[0];i++) ans*=n,ans%=MD; 64 cout<<ans; 65 return 0; 66 }