d018:
例題 P-2-9. 子集合乘積 (折半枚舉) (@@)
內容
輸入 $n$ 個正整數 $A[1 \cdots n]$，以及一個質數 $P$，請計算 $A$ 中元素各種組合中，有多少種組合其相乘積除以 $P$ 的餘數等於 $1$。每個元素可以選取或不選取但不可重複選，$A$ 中的數字可能重複。$P \leq 1000000009$，$0 < n < 37$。
輸入說明
第一行是 $n$ 與 $P$，第二行 $n$ 個整數是 $A[i]$，同行數字以空白間隔。
輸出說明
滿足條件的組合數，因為數字可能太大，請輸出該組合數除以 $P$ 的餘數。
範例輸入
#1
5 11 1 1 2 6 10
範例輸出
#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
公開 測資點#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
提示 ：
標籤: