d018: 例題 P-2-9. 子集合乘積 (折半枚舉) (@@)
Tags :
Accepted rate : 150人/181人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-03 08:46

Content

輸入 $n$ 個正整數 $A[1 \cdots n]$,以及一個質數 $P$,請計算 $A$ 中元素各種組合中,有多少種組合其相乘積除以 $P$ 的餘數等於 $1$。每個元素可以選取或不選取但不可重複選,$A$ 中的數字可能重複。$P \leq 1000000009$,$0 < n < 37$。

Input

第一行是 $n$ 與 $P$,第二行 $n$ 個整數是 $A[i]$,同行數字以空白間隔。

Output

滿足條件的組合數,因為數字可能太大,請輸出該組合數除以 $P$ 的餘數。

Sample Input #1
5 11
1 1 2 6 10
Sample Output #1
7
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


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