No.1631 Sorting Integers (Multiple of K) Easy
タグ : / 解いたユーザー数 89
作問者 :
とりゐ
/ テスター :
mugen_1337
re_re0101
👑 Note
Sorting Integer (multiple of K) is split into Easy and Hard versions by 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$
Problem Statement
There are $N$ positive integers of $1$ digit. Among them, $c_i$ are equal to $i$ $(1\leq i\leq9)$. When these $N$ integers are rearranged and regarded as an $N$-digit integer $M$ in base $10$, how many of them 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^3$
- $c_i\geq0$
- $\displaystyle \sum_{i=1}^9 c_i=N$
- All inputs are integers.
Output
Output the number 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 $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 digit $1$ appears $1$ time and the digit $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 $1$ time, and there are $24$ possible values of $M$. None of these is a multiple of $3$.
Sample 4
Input
9 123 1 1 1 1 1 1 1 1 1
Output
8832
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。