h997. 國小排列組合 - 高中生程式解題系統

內容

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

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

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

球不同，箱子不同
球相同，箱子不同
球不同，箱子相同
球相同，箱子相同

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

輸入說明

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

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

輸出說明

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

範例輸入 #1

5 10 1

範例輸出 #1

1 32 243 1024 3125 7776 16807 32768 59049 100000

範例輸入 #2

5 10 2

範例輸出 #2

1 6 21 56 126 252 462 792 1287 2002

範例輸入 #3

5 10 3

範例輸出 #3

1 16 41 51 52 52 52 52 52 52

範例輸入 #4

5 10 4

範例輸出 #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

提示：

$25 % ： t = 1$

$25 % ： t = 2$

$25 % ： t = 3$

$25 % ： t = 4$

標籤:

DP 排列組合數學

出處:

Caido [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」