有一位初階班電神，他在初階班時就自學刻線段樹，甚至還在上課時用手將整段程式碼寫了下來。大家都說他和$Frankie$一樣很電，但事實上，$Frankie$和他比起來就跟電渣一樣什麼都不是。某天，這位初階班電神對$Frankie$說了一句話：「我今天想到一個題目，輸入$n$為要前進幾格，$m$為可以擲幾次骰子$(1$~$6)$，然後輸出可以到達(含超過$n$)的機率。」
因為$Frankie$跟這位電神比起來實在是太爛了，但又不想要讓這位初階班電神覺得$Frankie$自己實在很爛，請你幫幫電渣$Frankie$求出這位初階班電神所出的題目答案吧！
本題多測資點多筆測資
第一行給你一數$T$代表共$T$筆測資
接下來$T$行每行給你兩個正整數$n$、$m$
分別代表目標格子以及擲骰子次數
輸出$T$行，每行有兩個正整數
第一個數為能抵達的方法數，而第二個數為總方法數，而兩數中間以一斜線做分隔 (這樣才像機率嘛)
兩者皆需$mod 10^9+7$
1 5 3
212/216
$Subtask:$
# $00:$ $1<m≤100$ $1≤n≤600$ $T=10^3$
# $01:$ $1<m≤1000$ $1≤n≤6000$ $T=10^4$
# $02:$ $1<m≤3000$ $1≤n≤18000$ $T=10^5$
# $03:$ $1<m≤5*10^3$ $1≤n≤3*10^4$ $T=10^6$
保證所有測資中，$n≤6m$
！此事為真實事件！
若想單純做$DP$的話，可以試著只做#$00$、#$01$這兩個測資點
這題壓到空間常數，絕對是我想提升題目難度，而不是懶得重出測資
這題的陣列要開到$400MB$左右，盡量嘗試壓縮自己使用的記憶體
開$n^2$的話一定爆掉，試著算算空間複雜度
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||