c623: 球球
Tags :
Accepted rate : 0人/1人 ( 0% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-04-14 19:34

Content

「把 $\color{black}{N}$ 顆相同的球分成 $\color{black}{M}$ 群,有多少種方法?
把 $\color{black}{N}$ 顆不同的球分成 $\color{black}{M}$ 群,有多少種方法?
把 $\color{black}{N}$ 顆相同的球放進 $\color{black}{M}$ 個相同的箱子(可以有空箱),有多少種方法?
把 $\color{black}{N}$ 顆相同或不同的球放進 $\color{black}{M}$ 個可能相同也可能不同的箱子(說不定能有空箱),存在多少種可行的方法?請輸出答案除以 $\color{black}{1000000007}$ 除以 $\color{black}{1000000000000007}$ 除以 $\color{black}{100000700000000700000000000000000000000000000000000000000007007}$ 的餘數。」

重臨人間的球球之神,今天又帶著許多球球來問你問題。

球球之神擁有 $\color{black}{n}$ 種不同顏色的球,現在想選出其中幾種做為球球世界的幸運色,接著讓每位居民從中挑一種配戴在身上(因為球球之神的球球太多了,所以即便大家都選相同的顏色也不會產生任何問題)。球球之神想知道的是,幸運色與居民選擇的組合有多少種可能性?

舉例來說,如果球球之神有黑白兩種顏色的球,而球球世界有三位居民,則有以下十種可能:

 幸運色  居民選擇 (居民一, 居民二, 居民三)
 {黑}  {(黑, 黑, 黑)}
 {白}  {(白, 白, 白)}
 {黑, 白}              {(黑, 黑, 黑), (黑, 黑, 白), (黑, 白, 黑), (黑, 白, 白), (白, 黑, 黑), (白, 黑, 白), (白, 白, 黑), (白, 白, 白)}

若幸運色為黑色或白色,居民選擇都只有一種可能;若幸運色為黑白兩色,居民選擇有八種可能。

注意到三位居民分別選擇 (黑, 黑, 黑) 時,當日幸運色可為 {黑} 或 {黑, 白},應視為不同狀況。

 

Input

只有兩個正整數 $\color{black}{n, \space c}$ 分別為顏色數量和居民數量。

Output

因為組合的可能性很多(甚至比球球還多),請對 $\color{black}{10^9+7}$ 取餘數再輸出。

Sample Input
範例輸入一:
2 3

範例輸入二:
5 1
Sample Output
範例輸出一:
10

範例輸出二:
80
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (4%): 1.5s , <1K
不公開 測資點#1 (4%): 1.5s , <1K
不公開 測資點#2 (7%): 1.5s , <1K
不公開 測資點#3 (7%): 1.5s , <1K
不公開 測資點#4 (10%): 1.5s , <1K
不公開 測資點#5 (10%): 1.5s , <1K
不公開 測資點#6 (8%): 1.5s , <1K
不公開 測資點#7 (8%): 1.5s , <1K
不公開 測資點#8 (7%): 1.5s , <1K
不公開 測資點#9 (7%): 1.5s , <1K
不公開 測資點#10 (7%): 1.5s , <1K
不公開 測資點#11 (7%): 1.5s , <1K
不公開 測資點#12 (7%): 1.5s , <1M
不公開 測資點#13 (7%): 1.5s , <1M
Hint :

測資點 $\color{black}{0 \sim 1 (8\%)}$ ,$\color{black}{n \le 10, \space c \le 10}$

測資點 $\color{black}{2 \sim 3 (14\%)}$ ,$\color{black}{n \le 1000, \space c \le 1000}$

測資點 $\color{black}{4 \sim 5 (20\%)}$ ,$\color{black}{n \le 10^6, \space c \le 10^9}$

測資點 $\color{black}{6 \sim 7 (16\%)}$ ,$\color{black}{n \le 10^9, \space c \le 2}$

測資點 $\color{black}{8 \sim 10 (21\%)}$ ,$\color{black}{n \le 10^9, \space c \le 1000}$

測資點 $\color{black}{11 \sim 13 (21\%)}$ ,$\color{black}{n \le 10^{1000000}, \space c \le 100000}$

Tags:
出處:
[管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」