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; } };