各位有聽過21點吧?
沒有也沒關係，因為我們不是要玩21點
現在盤面上有N個位置，這些位置最多可以放一張牌，也可以不放
你只有三種點數的牌可以放，分別是 A , B 和 A+B
A，B 和 A+B 這三種牌的數量是無限的
目標是要讓這些牌的和是K，沒牌的位置的就當0點計算
問你可不可行就太easy了
所以請你求出有幾種方法可以滿足條件
每個位置視為相異，比如1,2,3和1,3,2就當兩種方法
第一行輸入T 代表有幾筆測資
接下來 T 行
每行有 N , A , B , K
分別代表N張牌，以及點數 A, B 和欲達成的K點
測資範圍:
第00筆到第03測資:T≤20,1≤N,A,B≤105,0≤K≤1010
第04筆到第05測資:T≤1000,1≤N,A,B≤102,0≤K≤104
輸出滿足點數和為K的方法數，答案請modulo(取模) 109+7
2 3 1 2 3 4 1 4 7
10 16
Sample test 1:
3 1 2 3
放1 A,1 B ->6種
AB0
A0B
AB0
BA0
B0A
BA0
放 1 (A+B) ->3種
A+B 0 0
0 A+B 0
0 0 A+B
AAA的1種
6+3+1=10
Sample test 2:
4 1 4 7
放3A1B ->4種
放1 A+B 2 A ->12種
共4+12=16種
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||