問題一覧 > 通常問題

No.1631 Sorting Integers (Multiple of K) Easy

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 62
作問者 : とりゐとりゐ / テスター : mugen_1337mugen_1337 re_re0101re_re0101 遭難者遭難者
0 ProblemId : 6735 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-28 02:55:30

注意

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$
また,この問題の TL は 3sec です.

問題文

$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^3$
  • $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 123
1 1 1 1 1 1 1 1 1
出力
8832

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。