Pocket Book

codeforces program

問題

  • Pocket Book
  • n人の名前のリストがある。全ての名前はm文字から成る。
  • i, j, k: 1 <= i, j <= n, 1 <= k <= m を選んで、i番目の名前の1...k文字とj番目の名前の1...k文字を入れ替えることが出来る。
  • この操作を何回でもやってよい。
  • 最終的に1番目に現れうる名前は何通りあるか

方針

以下がポイント

  • 最初に k = m と選ぶと、m文字目に現れている任意の文字を1番目の名前のm文字目に移動させることが出来る。
  • 次に k = m-1と選ぶと、m-1文字目に現れている任意の文字を1番目の名前のm-1文字目に移動させる事ができる。
    • この時1番目の名前のm文字目は影響を受けない。

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>


typedef unsigned long long ull;

using namespace std;

int main(int argc, char *argv[]){
  int n, m;
  cin >> n >> m;
  vector<string> names(n);
  for(int i = 0; i < n; i++){
    cin >> names[i];
  }

  ull buf = 1;
  for(int j = m-1; j >= 0; j--){
    set<char> temp;
    for(int i = 0; i < n; i++){
      temp.insert(names[i][j]);
    }
    buf *= temp.size();
    buf %= 1000000007;
  }

  cout << buf << endl;

  return 0;
}