CFR 757 C. Felicity is Coming! ( Hash )

Problem - C - Codeforces

題意：
有 N 個道館，裡面都有若干隻怪獸。怪獸用一個整數描述，表示品種。現在要定義一個一對一 ( 雙向 ) 函數，把 { 1, 2, .. M } 映射到任意一個 [ 1, M ] 的排列。求有多少種這樣的一對一函數，滿足分別將每個道館的怪獸經過函數變異品種後，任意一個道館的任意一個品種的數量都不變。

資料規模：
道館數量 1 ≤ N ≤ 1e5
品種數量 1 ≤ M ≤ 1e6
總怪獸數量 1 ≤ Sigma{ G } ≤ 5e5
TL: 2000 ms
ML: 256 MB

解法：
若且唯若兩個品種分別在所有道館裡出現的次數相同，才可以屬於同一個群。同一個群的怪獸一定可以任意排列，所以如果該群有 n 隻怪獸，答案就乘上 n !。至於計算兩個品種在所有道館分別是否出現次數相同，可以分開來計算好特徵值之後進行比對。特徵值便是對在每個道館出現的次數計算的雜湊函數。

時間 / 空間複雜度：
O( Sigma{ G } + M lg M )

注意：
この人怖い...

const int MOD7 = ( int ) 1e9 + 7;

int N, M;
vvi G;

void init(){
  cin >> N >> M;
  G = vvi( N );
  for( int i = 0; i < N; ++i ){
    int sz; cin >> sz;
    G[ i ] = vi( sz );
    for( int j = 0; j < sz; ++j ){
      cin >> G[ i ][ j ];
    }
  }
}

const int BASE = ( int ) 1e9 + 7;
const int MOD[] = { ( int ) 1e9 + 9, 15485863 };

vp trait;

void preprocess(){
  trait = vp( M + 1 );
  int base[] = { 1, 1 };
  for( int i = 0; i < N; ++i ){
    map< int, int > cnt;
    for( int j = 0; j < G[ i ].size(); ++j ){
      ++cnt[ G[ i ][ j ] ];
    }
    for( auto it = cnt.begin(); it != cnt.end(); ++it ){
      ( trait[ it->first ].first += 1LL * it->second * base[ 0 ] % MOD[ 0 ] ) %= MOD[ 0 ];
      ( trait[ it->first ].second += 1LL * it->second * base[ 1 ] % MOD[ 1 ] ) %= MOD[ 1 ];
    }
    base[ 0 ] = 1LL * base[ 0 ] * BASE % MOD[ 0 ];
    base[ 1 ] = 1LL * base[ 1 ] * BASE % MOD[ 1 ];
  }
  map< pii, set< int > > trait2pool;
  for( int i = 1; i <= M; ++i ){
    trait2pool[ trait[ i ] ].emplace( i );
  }
  vi fact( M + 1 );
  fact[ 0 ] = 1;
  for( int i = 1; i <= M; ++i ){
    fact[ i ] = 1LL * fact[ i - 1 ] * i % MOD7;
  }
  int ans = 1;
  for( auto it = trait2pool.begin(); it != trait2pool.end(); ++it ){
    ans = 1LL * fact[ it->second.size() ] * ans % MOD7;
  }
  cout << ans << endl; 
}