PKU 3092 Non-divisible 2-3 Power Sums

問題

与えられた数nを、
n=Σ2^ni 3^miの形の和で表せ。
ただし、任意の互いに異なるi, jについて2^ni 3^miは2^nj 3^mjを割り切ってはならない。

制約条件

n＜2^31

方針

和の項を3の指数が小さい順に並べる。
ここで、2の指数が大きい順に並んでいないといけない。

3^m0で全体をくくると、
n = 3^m0 Σ2^ni 3^(mi-m0)となり、同じ問題で、サイズが小さいものに還元される。
したがって、次のようなメモ化再帰によって解けばいい。

rec(n, m) := 2の指数をm以下にして、nという数を和の形で表せるかどうか。
nは大きいが、m≦31で、nも指数的に減少するので、状態数はあまり多くない。

ソースコード

map<pi, pi> dp;
pi rec(int n, int two){
	if(dp.count(mp(n, two))) return dp[mp(n, two)];
	pi &res = dp[mp(n, two)];
	
	if(n == 0) return res = mp(0, 0);
	if(two == 0) return res = mp(-1, 0); // fail;
	
	rep(i, two){
		int nxt = n - (1 << i);
		if(nxt < 0 || nxt % 3) continue;
		while(nxt % 3 == 0){
			nxt /= 3;
			pi tmp = rec(nxt, i);
			if(tmp.first >= 0) return res = mp(nxt, i);
		}
	}
	return res = mp(-1, 0);
	
}

int main()
{
	int CS;
	cin >> CS;
	rep(cs, CS){
		int n;
		cin >> n;
		
		int three = 0;
		while(n % 3 == 0) n /= 3, three++;
		pi cur = mp(n, 31);
		vector<pi> ans;
		
		while(1){
			pi next = rec(cur.first, cur.second);
			int d = cur.first - (1 << next.second);
			int nt = three;
			while(d > next.first) d /= 3, nt++;
			ans.pb(mp(next.second, three));
			cur = next;
			three = nt;
			if(cur.first == 0) break;
		}
		
		printf("%d %d", cs + 1, ans.size());
		rep(i, ans.size()){
			printf(" [%d,%d]", ans[i].first, ans[i].second);
		}
		puts("");
	}
	return 0;
}