うーん、考え方はあってるのに本番しょうもないミスで落とした。
https://community.topcoder.com/stat?c=problem_statement&pm=17671
問題
01で構成される文字列Sを、以下のように定める。
非負整数のうち、二進数表記したときに1が連続する箇所がないようなものを小さい順に考える。
それぞれ二進数表記したものを連結してSとする。
正整数A,Bが与えられるので、SのうちA文字目以上B文字目未満の位置において1の登場回数を求めよ。
解法
f(n) := Sのprefix n文字中における1の登場回数
とすると、解はf(B-1)-f(A-1)である。
あとはf(n)を求めよう。
以下を考える。
cnt(k) := 二進数表記でk桁になるようなLeading Zeroを含まない正整数のうち、1が連続する箇所がないものの総数
sum(k) := cnt(k)が該当する整数の二進数表記における1の登場回数
これは最上位から二番目の1の登場箇所を総当たりすることを考えれば、容易にDPで求めることができる。
また、kを70程度まで考えるとk*cnt(k)の総和がBの上限を超えるので、そこまで考えればよい。
あとはこれらをもとにf(n)を求めよう。
S[n]がちょうどk桁の整数の二進数表記である場合、sum(1)+sum(2)+....+sum(k-1)の分はf(n)に計上される。
あとは、k桁の整数の二進数表記のうち、桁数の総数がnを超えない範囲でカウントしていこう。
その際、再帰的に上の桁から1がどこにあるかを求めて行こう。
ll pat[100]; ll sum[100]; int N; class SparseOnes { public: int hoge2(ll v) { ll ov=v; ll val=0; ll id=0; v--; int i,j; for(i=1;i<=N;i++) { if(v>=i*pat[i]) { v-=i*pat[i]; } else { id=v%i; val=1LL<<(i-1); int la=i-1; v/=i; v++; while(v) { v--; if(v==0) break; for(j=0;j<la-1;j++) { if(v<=pat[j+1]) { val|=1LL<<j; la=j; break; } v-=pat[j+1]; } } break; } } int cnt=0; int ret=0; for(i=60;i>=0;i--) { if(val&(1LL<<i)) cnt=1; if(cnt) { if(id==0) { ret=(val>>i)&1; break; } id--; } } return ret; } ll hoge(ll v) { if(v<=0) return 0; ll ov=v; ll ret=0; int i,j; for(i=1;i<=N&&v;i++) { if(v>=i*pat[i]) { ret+=sum[i]; v-=i*pat[i]; } else { ll num=v/i; ll lef=v%i; if(lef) { int add=i-lef; num++; for(j=1;j<=add;j++) ret-=hoge2(ov+j); } ll cur=1LL<<(i-1); int la=i-1; int bit=1; while(num) { num--; ret+=bit; if(num==0) break; for(j=0;j<la-1;j++) { if(num<=pat[j+1]) { cur|=1LL<<j; la=j; bit++; break; } else { ret+=sum[j+1]+bit*pat[j+1]; num-=pat[j+1]; } } } break; } } return ret; } long long count(long long A, long long B) { ZERO(pat); ZERO(sum); pat[1]=sum[1]=1; int i,j; for(i=2;i<=99;i++) { pat[i]=1; sum[i]=1; for(j=1;j<=i-2;j++) { pat[i]+=pat[j]; sum[i]+=sum[j]+pat[j]; } if(pat[i]>=1LL<<50) { N=i; break; } } return hoge(B-1)-hoge(A-1); } }
まとめ
やることはすぐ思いついたけど、正確な実装に割と手間取った。