The question is this-> [757C](http://www.codeforces.com/contest/757/problem/C)↵
↵
I am unable to understand anything in the editorial, as well as the given code. Can someone please help? ↵
↵
↵
↵
This is the editorial-> ↵
↵
Consider a valid evolution plan f. Let c[p, g] be the number of times Pokemon p appears in gym g. If f(p) = q then .↵
Now consider a group of Pokemon P such that all of them occur equal number of times in each gym (i.e. for each ). Any permutation of this group would be a valid bijection.↵
Say we have groups s1, s2, s3, ..., then the answer would be |s1|! |s2|! |s3|! ... mod 109 + 7.↵
For implementing groups, we can use vector < vector < int > > and for i-th pokemon, add the index of the gym to i-th vector.↵
Now we need to find which of these vectors are equal. If we have the sorted vector < vector < int > > , we can find equal elements by iterating over it and comparing adjacent elements.↵
Consider the merge step of merge sort. For a comparison between 2 vectors v1 and v2, we cover at least min(v1.size(), v2.size()) elements. Hence work is done at each level. There are levels.↵
Bonus : Try proving the time complexity for quicksort as well.↵
Authors's code:↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define PB push_back↵
#define ALL(X) X.begin(), X.end()↵
↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
const int N = 1e6;↵
const LL MOD = 1e9 + 7;↵
LL fact[N+1];↵
int main()↵
{↵
fast_io;↵
fact[0] = fact[1] = 1;↵
for(LL i=2;i<=N;i++)↵
fact[i] = (fact[i-1]*i)%MOD;↵
int n,m;↵
cin >> n >> m;↵
vector< vector<int> > x(m);↵
for(int i=0;i<n;i++) {↵
int s;↵
cin >> s;↵
for(int j=0;j<s;j++) {↵
int t;↵
cin >> t;↵
x[t-1].PB(i);↵
}↵
}↵
for(int i=0;i<m;i++)↵
sort(ALL(x[i]));↵
sort(ALL(x));↵
LL ans = 1;↵
LL sm = 1;↵
for(int i=1;i<m;i++) {↵
if(x[i]==x[i-1])↵
sm++;↵
else↵
ans = (ans*fact[sm])%MOD, sm = 1;↵
}↵
ans = (ans*fact[sm])%MOD;↵
cout << ans << endl;↵
return 0;↵
}↵
↵
I am unable to understand anything in the editorial, as well as the given code. Can someone please help? ↵
↵
↵
This is the editorial-> ↵
↵
Consider a valid evolution plan f. Let c[p, g] be the number of times Pokemon p appears in gym g. If f(p) = q then .↵
Now consider a group of Pokemon P such that all of them occur equal number of times in each gym (i.e. for each ). Any permutation of this group would be a valid bijection.↵
Say we have groups s1, s2, s3, ..., then the answer would be |s1|! |s2|! |s3|! ... mod 109 + 7.↵
For implementing groups, we can use vector < vector < int > > and for i-th pokemon, add the index of the gym to i-th vector.↵
Now we need to find which of these vectors are equal. If we have the sorted vector < vector < int > > , we can find equal elements by iterating over it and comparing adjacent elements.↵
Consider the merge step of merge sort. For a comparison between 2 vectors v1 and v2, we cover at least min(v1.size(), v2.size()) elements. Hence work is done at each level. There are levels.↵
Bonus : Try proving the time complexity for quicksort as well.↵
Authors's code:↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long LL;↵
↵
#define PB push_back↵
#define ALL(X) X.begin(), X.end()↵
↵
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)↵
↵
const int N = 1e6;↵
const LL MOD = 1e9 + 7;↵
LL fact[N+1];↵
int main()↵
{↵
fast_io;↵
fact[0] = fact[1] = 1;↵
for(LL i=2;i<=N;i++)↵
fact[i] = (fact[i-1]*i)%MOD;↵
int n,m;↵
cin >> n >> m;↵
vector< vector<int> > x(m);↵
for(int i=0;i<n;i++) {↵
int s;↵
cin >> s;↵
for(int j=0;j<s;j++) {↵
int t;↵
cin >> t;↵
x[t-1].PB(i);↵
}↵
}↵
for(int i=0;i<m;i++)↵
sort(ALL(x[i]));↵
sort(ALL(x));↵
LL ans = 1;↵
LL sm = 1;↵
for(int i=1;i<m;i++) {↵
if(x[i]==x[i-1])↵
sm++;↵
else↵
ans = (ans*fact[sm])%MOD, sm = 1;↵
}↵
ans = (ans*fact[sm])%MOD;↵
cout << ans << endl;↵
return 0;↵
}↵
