Codeforces 126 D. Fibonacci Sums

Codeforces 動的計画法

問題

与えられた数nを、異なるフィボナッチ数の和で表す表し方は何通りあるか、求めよ。

制約条件

n≦10^19

方針

フィボナッチ進数的なもの。
全ての整数はフィボナッチ進数で表せ、しかも各桁は0または1で、連続する1がない形に出来る。とかtopcoderの何かのeditorialに書いてあった。


まずは、フィボナッチ進数の正規形（上のような形）で与えられたnを表し、
その正規形を何通りに変形できるかを動的計画法で求める。


dp[i][j]を、i桁目までを表し、今までの繰り下がりのビットがjであるような表し方の数とする。
これを更新していけばいい。


jは2ビット分（今のビットと、その一つ下のビット）だけ覚えておけばよい。
正規形のi桁目に1が立っていたらjの上位ビットに1を加える。


更新は以下のような感じ。

  • jが2 1だったらこれはどうやっても異なるフィボナッチ数の和にならないので打ち切り。
  • jが1 1だったら上位の1はi桁目を1にするのに使わなければならない。
  • jが1 0のときは1をi桁目に書くか、下の桁に持ち越すことができる。
  • その場合次のjは1 1になる。
  • jが2 0だったら、上位の1の一つをi桁目で使って、もう一つを下の桁に持ち越す。

ソースコード

int d[100];
ll f[100], dp[100][4];

void run()
{
	f[0] = 1;
	f[1] = 2;
	rep(i, 90) f[i + 2] = f[i + 1] + f[i];
	
	int cs;
	cin >> cs;
	while(cs--){
		memset(dp, 0, sizeof(dp));
		memset(d, 0, sizeof(d));
		
		ll n;
		cin >> n;
		int m = 0;
		for(; f[m] <= n; m++);
		
		rep(i, m) if(n >= f[m - i - 1]){
			d[i] = 1;
			n -= f[m - i - 1];
		}
		
		dp[0][0] = 1;
		rep(i, m) rep(j, 4) if(dp[i][j]){
			int b1 = j >> 1, b2 = j & 1;
			if(b1 && b2 && d[i]) continue;
			b1 += d[i];
			
			if(b1 && !b2) dp[i + 1][3] += dp[i][j];
			if(b1 < 2) dp[i + 1][b2 * 2] += dp[i][j];
		}
		cout << dp[m][0] << endl;
	}
}