Unable to understand the editorial

Правка en1, от skpro19, 2017-08-22 13:49:32

The question is this-> 757C

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 > 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; }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский skpro19 2017-08-22 14:13:09 1961
en1 Английский skpro19 2017-08-22 13:49:32 2188 Initial revision (published)