Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-03-03SRM534 Div1(Practice)

SRM534 Div1 500 EllysNumbers

| 17:24 | SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) SRM534 Div1 500 EllysNumbers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

special numberは値が小さいので全部素因数分解する

ここで登場する素因数で、nが割り切れなければそもそも無理なので0

nが割り切れるならば1になるまで割り切って、素因数分解することができる

あとは互いに素ということなので、同じ素因数を含まないように要素を組み合わせる必要がある

ということは、例えばn=2^3*3^2*5とかであれば、2^3や3^2や5をひとまとまりとして考えればいい

このような素因数は、10^18でもせいぜい15個くらいにしか分解できない

なので、2^15くらいでビットDPすればいい


実装は結構ハードだった・・・


ソースコード

ll dp[2][1<<16];

template <class T> vector <T> strspl(string str) {
	vector <T> res;
	istringstream iss(str);
	copy(istream_iterator <T>(iss), istream_iterator <T>(), back_inserter(res));
	return res;
}

vector <pair <ll, int> > factorp(ll n) {
	vector <pair <ll, int> > f;

	for(ll i=2; i*i<=n; i++) {
		int cnt=0;
		while(n%i==0) { n/=i; cnt++; }
		if(cnt>0) f.push_back(make_pair(i, cnt));
	}
	if(n>1) f.push_back(make_pair(n, 1));

	return f;
}

class EllysNumbers {
public:
	long long getSubsets(long long N, vector <string> special) {
		long long res;
		string s=accumulate(special.begin(), special.end(), string());
		vector <int> vi=strspl <int>(s);
		int n=vi.size();
		sort(vi.begin(), vi.end());

		vector <vector <pair <ll, int> > > factv;
		vector <ll> fact;

		for(int i=0; i<n; i++) {
			factv.push_back(factorp(vi[i]));
			for(int j=0; j<(int)factv[i].size(); j++) fact.push_back(factv[i][j].first);
		}
		sort(fact.begin(), fact.end());
		fact.erase(unique(fact.begin(), fact.end()), fact.end());

		vector <pair <ll, int> > nfact;
		for(int i=0; i<(int)fact.size(); i++) {
			int cnt=0;
			while(N%fact[i]==0) {cnt++; N/=fact[i]; }
			if(cnt) nfact.push_back(make_pair(fact[i], cnt));
		}
		if(N!=1) return 0;

		int nfacts=nfact.size();
		vector <int> fmask(n);
		int canapp[510]={0};
		for(int i=0; i<n; i++) {
			canapp[i]=1;
			for(int j=0; j<(int)factv[i].size(); j++) {
				bool ok=false;
				int idx=-1;
				for(int k=0; k<nfacts; k++) {
					if(factv[i][j]==nfact[k]) {ok=true; idx=k; }
				}
				if(!ok) {canapp[i]=0; break; }
				fmask[i]|=(1<<idx);
			}
		}

		memset(dp[0], 0, sizeof(dp[0]));
		dp[0][(1<<nfacts)-1]=1;
		for(int d=0; d<n; d++) {
			memcpy(dp[(d+1)&1], dp[d&1], sizeof(dp[d&1]));
			if(!canapp[d]) continue;
			for(int mask=0; mask<(1<<nfacts); mask++) {
				if((mask&fmask[d])==fmask[d]) dp[(d+1)&1][mask^fmask[d]]+=dp[d&1][mask];
			}
		}

		res=dp[n&1][0];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120303