d020. P_2_9 子集合乘積(折半枚舉)

Content

輸入 n 個正整數 A[1..n]，以及一個質數 P，請計算 A 中元素各種組合中，有多少種組合其相乘積除以 P 的餘數等於 1。每個元素可以選取或不選取但不可重複選，A 中的數字可能重複。P<=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

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.5s , <1K
公開測資點#1 (20%): 1.5s , <1K
公開測資點#2 (20%): 1.5s , <1K
公開測資點#3 (20%): 1.5s , <1K
公開測資點#4 (20%): 1.5s , <1K

Hint ：

Tags:

ch2

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

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