h996. 幼稚園排列組合 - 高中生程式解題系統

內容

這是國小排列組合的前傳，因為是貓咪讀的幼稚園比較有錢，所以 $n, m$ 都比較大。

ㄇㄠㄇㄧ😺是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的吉娃娃、兩歲時發明了「倒墨水」的遊戲，而現在要講的，是ㄇㄠㄇㄧ😺在ㄧㄡˋㄓˋㄩㄢˊㄓㄨㄥㄅㄢ的故事。

有一天ㄇㄠㄇㄧ😺看到讀國中的哥哥在寫數數數字的回家作業 $\text{(Number counTing and wriTing}$，簡稱 $\text{NTT)}$，發現 $1000$ 題裡面竟然錯了 $24$ 題，於是哥哥就把ㄇㄠㄇㄧ😺帶到ㄧㄡˋㄓˋㄩㄢˊ了。

ㄇㄠㄇㄧ😺的老師是ㄌㄠˇㄕㄨˇㄌㄠˇㄕ🐭👩‍🏫🛐，他會教大家疊蛋糕、吃橘子和打排球，今天大家要做的就是手指運動，要把 $n$ 顆球球放到 $x$ 個箱子裡，且最後可以有空箱子。ㄇㄠㄇㄧ😺玩過幾輪後，發現這個遊戲有三種模式：

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

球相同和箱子相同的被ㄇㄠㄇㄧ😺吃掉了。給你球的數量和箱子數量最大會到多少，並且告訴你是哪一種模式的遊戲，你能幫助ㄇㄠㄇㄧ😺計算當 $x = 1\sim m$ 時分別有幾種方法放球球嗎？

輸入說明

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

$1 \leq n, m \leq 10^5$
$1 \leq t \leq 3$

輸出說明

輸出 $m$ 個整數代表當 $x = 1\sim m$ 時有幾種方法把球放進箱子，因為答案可能很大，請 $\bmod 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

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (11%): 2.0s , <1K
公開測資點#1 (11%): 2.0s , <1K
公開測資點#2 (11%): 2.0s , <1K
公開測資點#3 (11%): 2.0s , <1K
公開測資點#4 (11%): 2.0s , <1K
公開測資點#5 (11%): 2.0s , <1K
公開測資點#6 (3%): 3.0s , <1K
公開測資點#7 (3%): 3.0s , <1K
公開測資點#8 (4%): 3.0s , <1K
公開測資點#9 (4%): 3.0s , <1K
公開測資點#10 (4%): 3.0s , <1K
公開測資點#11 (4%): 3.0s , <1K
公開測資點#12 (4%): 3.0s , <1K
公開測資點#13 (4%): 3.0s , <1K
公開測資點#14 (4%): 3.0s , <1K

提示：

$33\%：t = 1$

$33\%：t = 2$

$34\%：t = 3$

標籤:

NTT 中國剩餘定理排列組合數學

出處:

Caido [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

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