問題一覧 > 通常問題

No.1634 Sorting Integers (Multiple of K) Hard

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 35
作問者 : とりゐ / テスター : mugen_1337 re_re0101 👑 qand
お気に入りにしたユーザー ProblemId : 6736 / 自分の提出
問題文最終更新日: 2021-07-28 02:55:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 307 (順位表) の他の問題:

Note

Sorting Integer (multiple of K) is divided into Easy and Hard according to difficulty. The problem statement is the same, but the constraints differ.

  • (Easy) $1\leq N\leq 14,\ 1\leq K\leq 10^3$
  • (Hard) $1\leq N\leq 14,\ 1\leq K\leq 10^9$
Also, the TL for this problem is 3sec.

Problem Statement

There are $N$ positive integers of $1$ digit. Among them, $c_i$ are equal to $i$ $(1\leq i\leq9)$. Rearrange these $N$ integers and regard the result as an $N$-digit integer $M$ in base $10$. How many of these are such that $M$ is a multiple of $K$?

Input

$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$
  • All inputs are integers.

Output

Output the number of values of $M$ that are multiples of $K$.

Sample

Sample 1
Input
3 6
1 1 1 0 0 0 0 0 0
Output
2

Each of $1,2,3$ appears exactly $1$ time, and the possible values of $M$ are $123,132,213,231,312,321$. Among these, the multiples of $6$ are $132,312$, so there are $2$ of them.

Sample 2
Input
3 2
1 2 0 0 0 0 0 0 0
Output
2

The integer $1$ appears $1$ time and the integer $2$ appears $2$ times, and the possible values of $M$ are $122,212,221$. Among these, the multiples of $2$ are $122,212$, so there are $2$ of them.

Sample 3
Input
4 3
1 1 1 1 0 0 0 0 0
Output
0

Each of $1,2,3,4$ appears exactly $1$ time, and there are $24$ possible values of $M$. None of them is a multiple of $3$.

Sample 4
Input
9 123456
1 1 1 1 1 1 1 1 1
Output
8

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