TopCoder SRM 534 Div1 Medium EllysNumbers

これは割とすんなり。
http://community.topcoder.com/stat?c=problem_statement&pm=11787

問題

数Nの他、distinctな数の集合Sが与えられる。
Sの部分集合のうち、各要素が互いに疎で、かつ全部の積がNとなるものの数を求めよ。

解法

Nを素因数分解した値を(P1^Q1) * (P2^Q2) * ... (Pn^Qn)とする。
答えの部分集合に含まれる値S[i]は、以下の条件を満たさなければならない。

• S[i]が素因数にPjを持つとき、その数はQj、すなわちNが持つPjの数と一致しなければならない。
• S[i]の異なる要素は、同じPjを素因数に持たない。

よって、S[i]の各要素がNの各素因数Pjと同じものを同じ数Qj個ずつ持つかをbitmaskで表現する。
この時、Nの素因数でない数を素因数に持つS[i]や、素因数Pjを持つもののその数がQj個と異なるS[i]は答えの候補になりえないので外しておく。

2*3*5...と素数を小さい順にかけると、16番目、47まで掛けたところでN<=10^18を超えるので、NないしS[i]は素因数を高々16個までしか持たない。

これでS[i]を素因数の有無により最大16bitのbitmaskに変換できた。
後はこれらbitmaskをいくつか集めたとき、Nの素因数全部になるような組み合わせを単純なDPで処理していく。

vector<ll> split_int(const string &str, char delim){
	vector<ll> res;
	size_t current = 0, found;
	while((found = str.find_first_of(delim, current)) != string::npos){
		string s = string(str, current, found - current);
		res.push_back(atoi(s.c_str()));
		current = found + 1;
	}
	string s = string(str, current, str.size() - current);
	res.push_back(atoi(s.c_str()));
	return res;
}
string concatvec(vector <string> expr) { return accumulate(expr.begin(),expr.end(),string("")); }
map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	while(n%2==0) V[2]++,n/=2;
	for(ll i=3;i*i<=n;i+=2) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

ll dpdp[1<<20];
map<ll,int> T[501];

class EllysNumbers {
	public:
	long long getSubsets(long long n, vector <string> special) {
		int i,mask;
		
		ZERO(dpdp);
		dpdp[0]=1;
		
		vector<ll> S=split_int(concatvec(special),' ');
		sort(S.begin(),S.end());
		
		set<ll> S2;
		map<ll,int> D;
		
		FOR(i,S.size()) {
			T[i] = enumdiv(S[i]);
			ITR(it,T[i]) S2.insert(it->first);
		}
		
		ITR(it,S2) while(n%*it==0) D[*it]++, n/=*it;
		if(n>1) return 0;
		
		map<ll,int> D2;
		ITR(it,D) D2[it->first]=D2.size()-1;
		vector<int> B;
		FOR(i,S.size()) {
			int nm=0,ng=0;
			ITR(it,T[i]) {
				if(D.find(it->first)==D.end()) ng++;
				else {
					ng += D[it->first]!=it->second;
					nm |= 1<<D2[it->first];
				}
			}
			if(ng==0) B.push_back(nm);
		}
		FOR(i,B.size()) {
			for(mask=(1<<D.size())-1;mask>=0;mask--) {
				if((mask & B[i])==0) dpdp[mask|B[i]]+=dpdp[mask];
			}
		}
		
		return dpdp[(1<<D.size())-1];
	}
}

まとめ

この回、submitは多いけど正答率は意外と少な目。
なんかひっかけがあったのかな？