No.1518 Simple Combinatorics
タグ : / 解いたユーザー数 146
作問者 :
NatsubiSogan
/ テスター :
aspi
soraie_
👑 
Nachia
Problem Statement
You are given positive integers $N,K$.
You repeat the following operation exactly $K$ times.
- Choose an integer between $1$ and $N$, inclusive, uniformly at random (this choice is independent of the other operations). Write the chosen integer in a notebook.
Output the expected number of distinct integers written in the notebook after all operations are finished, multiplied by $N^K$ (it can be shown that this value is an integer), modulo $10^9+7$ (a prime).
Input
$N\ K$
- All inputs are integers.
- $1 \leq N,K \lt 10^9+7$
Output
Output the value of the expected value multiplied by $N^K$, modulo $10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
2 3
Output
14
There is $1$ way in which only $1$ appears, $1$ way in which only $2$ appears, and $6$ ways in which both appear, so the expected value is $\displaystyle \frac{1 \times 2 + 2 \times 6}{2^3} = \frac{14}{8}$. Multiplying this by $2^3 = 8$ gives the answer, $14$.
Sample 2
Input
1 100
Output
1
Nothing other than $1$ can be chosen.
Sample 3
Input
314159265 358979323
Output
733723634
Note that you should output the answer modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。