kmjp's blog

競技プログラミング参加記です

HackerRank RookieRank4 : D. Winning Hand of Cards

解き始めが遅いのでそれなりな順位。
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;
}

まとめ

空集合の扱いでミスした。