Unable to understand the editorial
Разница между en1 и en2, 1,961 символ(ов) изменены
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;↵
}↵

История

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