o638. B - 黃金題敘 - 高中生程式解題系統

內容

鹿乃子乃子虎視眈眈Shikanoko Nokonoko Koshitantan GIF - 鹿乃子乃子虎視眈眈Shikanoko nokonoko koshitantan My deer friend nokotan - Discover & Share GIFs

給你一個有 $n$ 個整數的陣列 $A = (a_{1}, a_{2}, . . ., a_{n})$ ，要從 $A$ 裡面考慮每個元素，都有選和不選兩種選擇，總共有 $2^{n}$ 種選法，想問你對於有幾個選法滿足：全部選到的數加總的值會落在 $l \sim r$ 之間(包含兩端) ? 請注意這裡定義全部都不選的值為 $0$ 。

Update : 發現很多 submission 沒注意到答案可能超過 $2^{32}$ 。

輸入說明

輸入第一行有一個正整數 $n$ 。

第一行有兩個正整數分別代表 $l, r$ ，中間以空白隔開。

最後有一行 $n$ 個整數，兩兩以空白隔開，第 $i$ 個數代表 $a_{i}$ $(1 \leq i \leq n)$ 。

$1 \leq n \leq 36$
$- 10^{14} \leq l \leq r \leq 10^{14}$
$- 10^{12} \leq a_{i} \leq 10^{12}$

輸出說明

輸出一個數代表方法數。

範例輸入 #1

3
2 4
-2 1 2

範例輸出 #1

範例輸入 #2

1
0 2
4

範例輸出 #2

測資資訊：

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

提示：

範例 # 1

其中有 $(1, 2)$ , $(2)$ 二個選法，總和會落在 $2 \sim 4$ 之間。

剩下 $6$ 種選法不符合條件。

範例 # 2

只有全部都不選的選法 $(= 0)$ 符合條件。

Authored by r1cky

標籤:

出處:

第二屆Chi怪壓常比賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
43122	nagga300@gma ... (nigger300)	o638	__解答	84	2024-10-17 14:32
43121	nagga300@gma ... (nigger300)	o638	__超載	86	2024-10-17 14:31