TopCoder SRM 612 Div2 Hard PowersOfTwo

なんかCodeforcesに出そうな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13042

問題

2の累乗である整数のみを含む集合Pが与えられる。
(Pは同じ数字を複数含む場合もある)

この集合の部分集合の和で得られる数値は何通りあるか答えよ。

解法

いわゆるナップサック問題だが、普通にDPすると最大2^50かかるので間に合わない。
ここではPの中身が2の累乗であることを利用して解いていく。

和を2進数表記したとき、下の桁から決めていくことを考える。
下の桁を0または1にしたとき、それぞれPの要素を用いていくつまで上の桁に繰り上がれるか、という条件をもとに計算していく。

状態としては(桁数,繰り上がり数)なので50^2程度で済む。

ll memo[65][65];

class PowersOfTwo {
	int num[65];
	public:
	ll dpdp(int dig,int nu) {
		if(dig>=60) return 1;
		if(nu<0) return 0;
		if(memo[dig][nu]>=0) return memo[dig][nu];
		
		int c=nu+num[dig];
		if(c==0) return memo[dig][nu] = dpdp(dig+1,0);
		return memo[dig][nu] = dpdp(dig+1,c/2)+dpdp(dig+1,(c-1)/2);
	}
	
	long long count(vector<long long> powers) {
		int i;
		ZERO(num);
		MINUS(memo);
		
		FOR(i,powers.size()) {
			int n=0;
			while(1LL<<(1+n)<=powers[i]) n++;
			num[n]++;
		}
		
		return dpdp(0,0);
	}
};

まとめ

正答率は4.23%とやたら低いのだが、案の定2^50行くコードを書いた人が多かったようだ。