e036. P-2-9. 子集合乘積(折半枚舉) (@@) - 花中程式設計挑戰系統

Content

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

Time limit: 1 秒

Input

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

Output

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

Sample Input

5 11
1 1 2 6 10

Sample Output

測資資訊：

記憶體限制： 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 ：

說明乘積等於 1 的組合有：(1), (1), (1,1), (2,6), (1,2,6), (1,2,6), (1,1,2,6)共 7 種

Tags:

搜尋

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

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