No.2120 Last 8 Digits of the Number of Combinations
タグ : / 解いたユーザー数 60
作問者 : 👑
p-adic
/ テスター :
testestest
Problem Statement
Positive integers $M,N$ are given as input.
A shop sells $M$ kinds of cakes, $1$ piece of each. Find the last $8$ digits of the total number of ways to choose $N$ cakes at this shop.
Input
The input is given from standard input in the following format:
$M$ $N$
Constraints
The input $M,N$ satisfies the following constraints:
- $M$ is a positive integer at most $10^7$
- $N$ is a positive integer at most $10^7$
Output
Print on $1$ line the last $8$ digits of the total number of ways to choose $N$ cakes at a shop that sells $M$ kinds of cakes, $1$ piece of each.
However, if the total is less than $10^7$, pad it with leading $0$ digits so that it has $8$ digits.
For example, if the total is $21$ ways, the value to print is $00000021$.
Print a newline at the end.
Sample
Sample 1
Input
7 1
Output
00000007
The total number of ways to choose $1$ cake from $7$ kinds of cakes, $1$ piece of each, is
$\displaystyle \frac{7}{1} = 7 $
ways, and its last $8$ digits are $00000007$.
Sample 2
Input
11 2
Output
00000055
The total number of ways to choose $2$ cakes from $11$ kinds of cakes, $1$ piece of each, is
$\displaystyle \frac{11 \times 10}{2 \times 1} = 55 $
ways, and its last $8$ digits are $00000055$.
Sample 3
Input
100 6
Output
92052400
The total number of ways to choose $6$ cakes from $100$ kinds of cakes, $1$ piece of each, is
$\displaystyle \frac{100 \times 99 \times 98 \times 97 \times 96 \times 95}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 1192052400 $
ways, and its last $8$ digits are $92052400$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。