C. Felicity is Coming!(灰常考验思维!!)

这道题只猜中了开头,思维还是没有那么深

最重要的就是要理解什么样的神奇宝贝($gym$)可以相互转换

$对于一个训练馆,只有当两个gym数量相同时才能转换。$

$对于所有训练场,只有两个gym出现的训练场集合相等时才能转换$

关于上面的两条性质的证明:

因为进化都是一对一

对于一个训练场,进化一定是一若干个环,环的出度要等于入度

所以只有gym相等才能存在于环中

对于所有训练场,如果gym出现的训练场都不相同

进化后gym的数量就会流失

反之,满足以上关系的gym间都可以相互转换

这样我们得到可以相互转换的若干个gym集合

每个集合内有 t i t_i ti​个元素,那么有 t i ! 种 排 列 方 式 , 因 为 在 内 部 转 移 都 满 足 t_i!种排列方式,因为在内部转移都满足 ti​!种排列方式,因为在内部转移都满足

集合间不贡献答案

#include 
using namespace std;
#define int long long
const int maxn=1e6+10;
const int mod=1e9+7;
int n,m;
vectora[maxn];
signed main()
{cin >> n >> m;for(int i=1;i<=n;i++){int x,y; cin >> x;while( x-- ){cin >> y;a[y].push_back(i);}}sort(a+1,a+1+m);int ans=1,t=1;for(int i=2;i<=m;i++){if( a[i]==a[i-1] ){t++;//增加了一种 ans = (ans*t)%mod;}else	t=1;}cout << ans;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！