c567: K點
Tags : 組合
Accepted rate : 4人/9人 ( 44% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-09-18 16:52

Content

各位有聽過21點吧?

沒有也沒關係,因為我們不是要玩21點

 

現在盤面上有N個位置,這些位置最多可以放一張牌,也可以不放

你只有三種點數的牌可以放,分別是 A , B 和 A+B

A,B 和 A+B 這三種牌的數量是無限的

目標是要讓這些牌的和是K,沒牌的位置的就當0點計算

 

問你可不可行就太easy了 

所以請你求出有幾種方法可以滿足條件

每個位置視為相異,比如1,2,3和1,3,2就當兩種方法

 

 

Input

第一行輸入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

 

 

 

Output

輸出滿足點數和為K的方法數,答案請modulo(取模) 109+7

 

Sample Input
2
3 1 2 3
4 1 4 7
Sample Output
10
16
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (15%): 1.0s , <1K
不公開 測資點#1 (15%): 1.0s , <1K
不公開 測資點#2 (15%): 0.2s , <1K
不公開 測資點#3 (15%): 0.2s , <1K
不公開 測資點#4 (15%): 1.0s , <1K
不公開 測資點#5 (15%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
Hint :

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種

 

Tags:
組合
出處:
107學年度板橋高中校內資訊學科能力競賽310573sao [管理者:
snail (蝸牛)
]


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