No.1634 Sorting Integers (Multiple of K) Hard
タグ : / 解いたユーザー数 33
作問者 :
とりゐ
/ テスター :
mugen_1337
re_re0101
遭難者
注意
Sorting Integer (multiple of K) には難易度によって Easy, Hard に分かれています．問題文は同じですが制約が異なります．
- (Easy) $1\leq N\leq 14,\ 1\leq K\leq 10^3$
- (Hard) $1\leq N\leq 14,\ 1\leq K\leq 10^9$
問題文
$1$ 桁の正整数が $N$ 個あります．このうち $i$ は $c_i$ 個です $(1\leq i\leq9)$．これら $N$ 個の整数を並べ替え，それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき，$M$ が $K$ の倍数となるようなものはいくつありますか．
入力
$N\ K$ $c_1\ c_2\ c_3\ c_4\ c_5\ c_6\ c_7\ c_8\ c_9$
- $1\leq N\leq 14$
- $1\leq K\leq 10^9$
- $c_i\geq0$
- $\displaystyle \sum_{i=1}^9 c_i=N$
- 入力は全て整数である
出力
$K$ の倍数となる $M$ の個数を出力してください．
サンプル
サンプル1
入力
3 6 1 1 1 0 0 0 0 0 0
出力
2
$1,2,3$ が $1$ つずつあり，$M$ として考えられるものは $123,132,213,231,312,321$ があります．このうち $6$ の倍数であるものは $132,312$ の $2$ つです．
サンプル2
入力
3 2 1 2 0 0 0 0 0 0 0
出力
2
$1$ が $1$ つ，$2$ が $2$ つあり，$M$ として考えられるものは $122,212,221$ があります．このうち $2$ の倍数であるものは $122,212$ の $2$ つです．
サンプル3
入力
4 3 1 1 1 1 0 0 0 0 0
出力
0
$1,2,3,4$ が $1$ つずつあり，$M$ として考えられるものは $24$ 通りあります．このうち $3$ の倍数であるものは存在しません，
サンプル4
入力
9 123456 1 1 1 1 1 1 1 1 1
出力
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。