h997: 國小排列組合
Tags : DP 排列組合 數學
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-01 23:33

Content

貓咪是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的吉娃娃、兩歲時發明了「倒墨水」的遊戲,而現在要講的,是貓咪在國小三年級的故事。

有一天貓咪看到讀大學的哥哥在寫數數數字的回家作業 $\text{(Number counTing and wriTing}$,簡稱 $\text{NTT)}$,發現 $1000$ 題裡面竟然錯了 $24$ 題,於是哥哥就把貓咪帶到國小了。

貓咪的老師是短頸鹿老師,他會教大家疊蛋糕、吃橘子和抓老鼠,今天大家要做的就是手指運動,要把 $n$ 顆球球放到 $x$ 個箱子裡,且最後可以有空箱子。貓咪玩過幾輪後,發現這個遊戲有四種模式:

  1. 球不同,箱子不同
  2. 球相同,箱子不同
  3. 球不同,箱子相同
  4. 球相同,箱子相同

給你球的數量和箱子數量最大會到多少,並且告訴你是哪一種模式的遊戲,你能幫助貓咪計算當 $x=1\sim m$ 時分別有幾種方法放球球嗎?

Input

輸入三個正整數 $n, m, t$, 代表有幾顆球、最多有幾個箱子,和哪一種模式的遊戲。

  • $1 \leq n, m \leq 2000$
  • $1 \leq t \leq 4$
Output

輸出 $m$ 個整數代表當 $x = 1\sim m$ 時有幾種方法把球放進箱子,因為答案可能很大,請 $\bmod 1000000007$ 後再輸出。

Sample Input #1
5 10 1
Sample Output #1
1 32 243 1024 3125 7776 16807 32768 59049 100000
Sample Input #2
5 10 2
Sample Output #2
1 6 21 56 126 252 462 792 1287 2002
Sample Input #3
5 10 3
Sample Output #3
1 16 41 51 52 52 52 52 52 52
Sample Input #4
5 10 4
Sample Output #4
1 3 5 6 7 7 7 7 7 7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (6%): 2.0s , <1K
公開 測資點#1 (6%): 2.0s , <1K
公開 測資點#2 (6%): 2.0s , <1K
公開 測資點#3 (7%): 2.0s , <1K
公開 測資點#4 (6%): 2.0s , <1K
公開 測資點#5 (6%): 2.0s , <1K
公開 測資點#6 (6%): 2.0s , <1K
公開 測資點#7 (7%): 2.0s , <1K
公開 測資點#8 (6%): 3.0s , <1K
公開 測資點#9 (6%): 3.0s , <1K
公開 測資點#10 (6%): 3.0s , <1K
公開 測資點#11 (7%): 3.0s , <1K
公開 測資點#12 (6%): 3.0s , <1K
公開 測資點#13 (6%): 3.0s , <1K
公開 測資點#14 (6%): 3.0s , <1K
公開 測資點#15 (7%): 3.0s , <1K
Hint :

$25\%:t = 1$

$25\%:t = 2$

$25\%:t = 3$

$25\%:t = 4$

Tags:
DP 排列組合 數學
出處:
Caido [管理者: becaido(Caido) ]


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