Bangladesh OI 2016 National Round pF. Batman and Robin ( Ad hoc )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意：
給你 L, A，代表字串的大小，以及可能字符集合大小。
接著給字串，以數字表示字符異同關係。
現在有人跟你說，他心裡想的字串消去某個字符後，恰好和你的字串裡消去某個字符後是一樣的。
求這個人心裡可能想的字串方案數，對 1e9 + 7 取模。

資料規模：
1 ≤ T ≤ 5
For easy version: 1 ≤ L ≤ 20 (easy), 1 ≤ A ≤ 26
For hard version: 1 ≤ L ≤ 60 (hard), 1 A ≤ 1e9
TL: 4000 ms
ML: 256 MB

解法：
換句話說，要不重複的算有多少種 W' 是 W 插入一個新的字後，刪除一個字得到的。
分兩種情況討論，將加入的是有在 W 裡面的元素，或非。
如果是不在 W 裡的元素，暴力算一次，然後乘上這樣的元素數量，加在答案上。
如果是，那麼也最多 L ^ 2 種，所以輕鬆暴力做。
暴力做法是枚舉要加入的元素、加入的位子、刪除的元素，用 vector 亂搞，然後用 set 維護。

時間 / 空間複雜度：
O( L ^ 3 lg L )

閒話：
一開始沒仔細看有 4000 ms，我還真瞎寫了噁爛 hash。

void solve(){
  int T; cin >> T;
  for( int kase = 1; kase <= T; ++kase ){
    int L, A; cin >> L >> A;
    vi W( L );
    for( int i = 0; i < L; ++i ){
      cin >> W[ i ];
    }
    set< int > exist;
    for( int i = 0; i < L; ++i ){
      exist.emplace( W[ i ] );
    }
    int ans = 0;
    set< vi > dict;
    for( int del = 0, add = ( int ) 1e9 + 1; del < L; ++del ){
      vi t;
      for( int i = 0; i < L; ++i ){
        if( i == del ) continue;
        t.emplace_back( W[ i ] );
      }
      for( int pos = 0; pos < L; ++pos ){
        vi f;
        for( int i = 0; i < L; ++i ){
          if( i == pos ){
            f.emplace_back( add );
          } else{
            f.emplace_back( t[ i > pos ? i - 1 : i ] );
          }
        }
        dict.emplace( f );
      }
    }
    ans = 1LL * dict.size() * ( A - exist.size() ) % MOD7;
    dict.clear();
    dict.emplace( W );
    for( int add : exist ){
      for( int del = 0; del < L; ++del ){
        vi t;
        for( int i = 0; i < L; ++i ){
          if( i == del ) continue;
          t.emplace_back( W[ i ] );
        }
        for( int pos = 0; pos < L; ++pos ){
          vi f;
          for( int i = 0; i < L; ++i ){
            if( i == pos ){
              f.emplace_back( add );
            } else{
              f.emplace_back( t[ i > pos ? i - 1 : i ] );
            }
          }
          dict.emplace( f );
        }
      }
    }   
    ( ans += dict.size() ) %= MOD7;
    cout << ans << endl;
  }
}