TopCoder SRM 632 Div2 Hard GoodSubset

典型問題？
http://community.topcoder.com/stat?c=problem_statement&pm=13396

問題

N要素の整数の集合d[i]と整数goodValueが与えられる。
d[i]の部分集合のうち、積がgoodValueとなるものの数を答えよ。

解法

DPで処理していく。

まずgoodValueの約数を列挙しておく。
あとはd[i]を順に見ていって組み合わせ数をdp[現在の積]に格納するだけ。
(現在の積)*d[i]がgoodValueの約数にならない場合は無視する。

計算量は約数列挙とDPでO(√goodValue + d(goodValue)*log(d(goodValue))**N)。
logはmapを使って配列の位置を求めるため。

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}


class GoodSubset {
	public:
	int numberOfSubsets(int goodValue, vector <int> d) {
		vector<ll> V=enumdiv(goodValue);
		ll mo=1000000007;
		map<ll,int> M;
		int i,j,k;
		FOR(i,V.size()) M[V[i]]=i;
		
		vector<ll> dp(V.size(),0);
		dp[0]=1;
		FOR(i,d.size()) {
			ll v=d[i];
			for(j=V.size()-1;j>=0;j--) if(goodValue%(V[j]*v)==0) dp[M[V[j]*v]]=(dp[M[V[j]*v]]+dp[j])%mo;
		}
		return (dp[V.size()-1]+(mo-(goodValue==1)))%mo;
	}
}

まとめ

これは割と簡単。