c567: K點
標籤 : 組合
通過比率 : 43% (3 人 / 7 人 ) (非即時)
評分方式:
Tolerant

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

內容

各位有聽過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
測資資訊:
記憶體限制: 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
提示 :

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種

 

標籤:
組合
出處:
107學年度板橋高中校內資訊學科能力競賽310573sao [編輯:
snail (蝸牛)
]


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