問題一覧 > 通常問題

No.1634 Sorting Integers (Multiple of K) Hard

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

注意

Sorting Integer (multiple of K) には難易度によって Easy, Hard に分かれています.問題文は同じですが制約が異なります.

  • (Easy) 1N14, 1K103
  • (Hard) 1N14, 1K109
また,この問題の TL は 3sec です.

問題文

1 桁の正整数が N 個あります.このうち ici 個です (1i9).これら N 個の整数を並べ替え,それを N 桁の 10 進法の整数 M とみなしたとき,MK の倍数となるようなものはいくつありますか.

入力

N K
c1 c2 c3 c4 c5 c6 c7 c8 c9

  • 1N14
  • 1K109
  • ci0
  • i=19ci=N
  • 入力は全て整数である

出力

K の倍数となる M の個数を出力してください.

サンプル

サンプル1
入力
3 6
1 1 1 0 0 0 0 0 0
出力
2

1,2,31 つずつあり,M として考えられるものは 123,132,213,231,312,321 があります.このうち 6 の倍数であるものは 132,3122 つです.

サンプル2
入力
3 2
1 2 0 0 0 0 0 0 0
出力
2

11 つ,22 つあり,M として考えられるものは 122,212,221 があります.このうち 2 の倍数であるものは 122,2122 つです.

サンプル3
入力
4 3
1 1 1 1 0 0 0 0 0
出力
0

1,2,3,41 つずつあり,M として考えられるものは 24 通りあります.このうち 3 の倍数であるものは存在しません,

サンプル4
入力
9 123456
1 1 1 1 1 1 1 1 1
出力
8

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