目次

• 問題
  • 入力
  • 出力
  • 入出力例
• 解説
• 計算量
• 解答

# 問題

https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_d

# 入力

N
K
c_1
c_2
...
c_N

• N - カードの枚数 ($4 \leq N \leq 10)
• K - 選ぶ枚数 ($2 \leq K \leq 4)
• c_i - カードに書かれた数字 ($1 \leq c_i \leq 99)

# 出力

N枚のカードからKを選んで自由に並び替えて出来る数字の数を答える問題です.
同じ数字が複数出来てもまとめて1と数えます.

# 入出力例

4
2
1
2
12
1

7

# 解説

単純に与えられたカードのすべての並べ方を試してみます.
そしてそこから先頭$K$個選んで数字を作ります.
それが初めて生成された数字ならカウントを+1していきます.
これですべてのカードの並べ方を試し終わった時カウントが答えになっているはずです.

すべてのカードの並べ方は$N!$通りです.
そしてK個選んだカードから数字を組み立てるためにはすべての数字をチェックする必要があるので計算量$O(K)$です.
合わせても$O(N! \cdot K)$なので間に合います.

# 計算量

実行時間: 52ms

$O(N! \cdot K)$

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 10
#define MAX_K 4

Int N, K;
vector<Int> C;
// 2桁 x 4つ
vector<bool> bucket(pow(10, 9), false);

void input() {
  cin >> N >> K;
  Int _c;
  while (cin >> _c) C.push_back(_c);
}

Int buildInt() {
  Int n = C.at(0);
  loop(k,1,K) {
    if (C.at(k) >= 10) n *= 100;
    else n *= 10;
    n += C.at(k);
  }
  return n;
}

Int bit() {
  sort(span_all(C));
  Int counter = 0;
  Int n = 0;
  do {
    n = buildInt();
    if (!bucket.at(n)) {
      bucket.at(n) = true;
      counter++;
    }
  } while (next_permutation(span_all(C)));

  return counter;
}

void solve() {
  cout << bit() << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}