內容
給你一個有 $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 ≤ n ≤ 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
範例輸入
#2
1 0 2 4
範例輸出
#2
1
測資資訊：
記憶體限制：
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
公開 測資點#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怪壓常比賽
[管理者：
liaoweichen1
...
(M_SQRT)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 43122 |
|
o638 | 29 | 2024-10-17 14:32 | |
| 43121 |
|
o638 | 38 | 2024-10-17 14:31 |