Hatena::Grouptopcoder

TopCoder Memo@kagamiz

03.13.2014 (Thu)

SRM 612 Div2 Hard - PowersOfTwo

| 22:04 | はてなブックマーク -  SRM 612 Div2 Hard - PowersOfTwo - TopCoder Memo@kagamiz

問題文 : PowersOfTwo

概要 :

2 のべきからなる配列 A が与えられる. これらを幾つか足しあわせて出来る数の総数を求めよ.

制約 :

1 ≦|A| ≦ 50

1 ≦ A_i ≦ 2^50

A_i は2 のべき


解法 :

まず, A を降順にソートする. そして

dp[i][j][k] := 上から i 桁目を, A_j 以降の数字で 2 進表現で k にする総数, としてメモ化再帰すればいい.

メモ化再帰を行うときは, 上の桁から確定させていくと実装が楽である.

計算量は, 桁数をD, 配列の大きさをN とすると, O(DN) となる. 今, 2^50 * 50 が表現できる数の上限であるから, 二進表現での最大の桁数は 56 桁以下であるから D ≦ 56 で, 十分高速であることが分かる.

コード :

#include <bits/stdc++.h>

using namespace std;
typedef long long lint;

class PowersOfTwo {
public:
	long long count(vector<lint>);
};

int n;
lint memo[64][64][2];
vector<lint> v;

lint countIt(int pos, int rem, int bit)
{
	if (pos < 0) return (!bit);
	if (rem < 0) rem = 63;
	
	lint &res = memo[pos][rem][bit];
	if (res >= 0) return (res);
	
	res = 0;
	lint target = bit ? (1ll << pos) : 0;
	int next = rem;
	while (target && next >= 0 && next != 63){
		if (v[next] <= target) target -= v[next];
		next--;
	}
	if (target) return (res = 0);
	res = countIt(pos - 1, next, 0) + countIt(pos - 1, next, 1);
	return (res);
}

long long PowersOfTwo::count(vector<lint> v) {
	sort(v.begin(), v.end());
	::v = v;
	
	n = v.size();
	memset(memo, -1, sizeof(memo));
	
	return (countIt(63, n - 1, 0));
}