解き始めが遅いのでそれなりな順位。
https://www.hackerrank.com/contests/rookierank-4/challenges/winning-hand-of-cards
問題
N個のカードがあり、それぞれ整数V[i]が書かれている。
このカードの部分集合のうち、書かれた数字の積を取ってmod Mを取るとXとなるのは何通りか。
解法
2^Nは大きいので全通り列挙できないが、Mはそこまで大きくない。
よって各カードに対し、それを取った場合と取らない場合における積のmod Mの組み合わせをDPすればO(NM)で解ける。
選び方として空集合は許可されないのでそれだけ取り除こう。
int N,M,X; int A[31]; int from[1010101]; int to[1010101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>X; to[1%M]=1; FOR(i,N) { memmove(from,to,sizeof(from)); cin>>x; x%=M; FOR(j,M) to[(1LL*x*j)%M]+=from[j]; } to[1%M]--; cout<<to[X]<<endl; }
まとめ
空集合の扱いでミスした。