TopCoder SRM 508 Div1 Medium YetAnotherORProblem

Div2 Hardの上位互換問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11379

問題

N要素の整数配列R[i]がある。

ここから、N要素の配列A[i]を作りたいが、その時以下の条件を満たさなければならない。

• 0 <= A[i] <= R[i]
• A[0] + A[1] + ... + A[N-1] = A[0] | A[1] | ... | A[N-1]

条件を満たすA[i]の組み合わせ数を答えよ。

解法

後者の条件より、A[0] | A[1] | ... | A[N-1]の2進数表記の各bitは、A[0]～A[N-1]の間に最大1個までしか登場しない。

R[i]の最上位ビットをM bit目とすると、A[i]のM bit目をセットする場合、残りA[i]の選択肢は0～A[i]-(1<

• 残りのRから、P bit目を最上位とするR[i]を選ぶ：
  • R[i]から(1<
  • その際、他に1<
• 「任意の値を取れる数」からP bit目を最上位とする数を選ぶか、もしくはP bit目は0にしておく
  • 1<
  • (任意の値を取れる数+1)に(P-1)bit目を再帰的に処理した値を掛け合わせる。

下記のコードは結構計算量が危なくて、mod計算を減らさないとTLEする。

ll mo=1000000009;
ll pows[64][64];

class YetAnotherORProblem {
	public:
	int N;
	
	ll dpdp(int bit,vector<ll>& R, int left) {
		ll ret=0;
		ll num=1LL<<bit;
		int i,j;
		
		if(bit<0) return 1;
		if(R.empty()) return pows[left+1][bit+1];
		
		int l2=0;
		vector<ll> V;
		V.reserve(16);
		
		FOR(i,R.size()) {
			if(R[i]>=num-1) l2++;
			else V.push_back(R[i]);
		}
		ret = (left+1) * dpdp(bit-1,V,left+l2) % mo;
		
		FOR(i,R.size()) if(R[i]>=num) {
			if(R[i]==num) ret += dpdp(bit-1,V,left+l2-1);
			else {
				V.push_back(R[i]-num);
				ret += dpdp(bit-1,V,left+l2-1);
				V.pop_back();
			}
			if(ret>=mo) ret -= mo;
		}
		return ret;
	}
	
	
	int countSequences(vector<long long> R) {
		int x,y;
		FOR(x,64) {
			pows[x][0]=1;
			FOR(y,63) pows[x][y+1]=(pows[x][y]*x)%mo;
		}
		N=R.size();
		return dpdp(59,R,0)%mo;
	}
};

まとめ

こういう問題はCodeforcesで出そう。