TopCoder SRM 622 Div1 Hard FibonacciXor

問題

fibonacci進法は以下の擬似コードで表されるような位取り記法である。

int[] toFibonacci(int d){
	
	for(int i = inf; i > 0; i--){
		if(fib[i] <= n){
			n -= fib[i];
			digit[i] = 1;
		}
		else digit[i] = 0;
	}
	return digit;
}

ここでfib[i]はi番目のフィボナッチ数(0, 1, 1, 2, 3, 5, 8, ...)を表す。


xをfibonacci進法で表したものを、二進法として解釈した数をg(x)とする。
与えられた正整数A, Bについて、Xor{g(i) | A≦i≦B}を求めよ。

制約条件

A, B≦10^15

方針

n未満のiについてxor{g(i)}をrec(i)でメモ化再帰して求める。


rec(i)は、iを[fib[j], fib[j + 1])の区間に分割してそれぞれxorを取ってやればよい。
上の桁からgreedyに取るアルゴリズムでfibonaaci進数に変換することが決まっているので、
[fib[j], fib[j + 1])の区間では、jの位が1になることは確定している。
よってこの区間のxorはrec(fib[j + 1] - fib[j])と、あとjの位に1(もし区間の長さが奇数なら)を(xorで)足せばよいだけ。


再帰の回数の見積もりがよくわからないのだけれど、なんかはやく終わる。
(fib[j + 1] - fib[j]の部分は毎回同じだし、それ以外の部分は上の1桁をgreedyに取るだけなので、多分状態数がlog(n)^2とか?)


fib[j]のjは最悪75とかなので二進数がlong longに入らない。
64桁ずつ分ける自前のクラスとかを定義しないとダメ。

ソースコード

struct LL{
	ll h, l;
	LL(ll h, ll l) : h(h), l(l){}
	LL() : h(0), l(0){};
	
	LL operator^(const LL &r){
		LL x(h, l);
		x.h ^= r.h;
		x.l ^= r.l;
		return x;
	}
	bool operator<(const LL &r) const{
		if(h != r.h) return h < r.h;
		return l < r.l;
	}
};

class FibonacciXor {
	public:
	
	static const int mod = (int)1e9 + 7;
	
	ll fib[80];
	map<ll, LL> dp;
	
	LL rec(ll n){
		if(dp.count(n)) return dp[n];
		LL &res = dp[n];
		
		if(n <= 1) return res = LL();
	
		res = LL();
		int idx;
		for(idx = 75; fib[idx] >= n; idx--);
		
		for(int i = 2; i <= idx; i++){
			
			res = res ^ rec(min(n, fib[i + 1]) - fib[i]);

			if((min(n, fib[i + 1]) - fib[i]) % 2 == 1){
				if(i - 2 >= 64) res.h ^= 1ull << (i - 66);
				else res.l ^= 1ull << (i - 2);
			}
		}
		return res;
	}
	int find(long long A, long long B) {
		fib[0] = 0;
		fib[1] = 1;
		rep(i, 75) fib[i + 2] = fib[i + 1] + fib[i];
		
		LL res = rec(B + 1) ^ rec(A);
		ll ans = res.h * ((((1ll << 32) % mod) << 32) % mod);
		ans = (ans + res.l) % mod;
		
		return ans;
	}
};