yukicoder : No.681 Fractal Gravity Glue

タイトルがヒントになっていることにAC後気づいた。
https://yukicoder.me/problems/no/681

問題

G(b,d)を以下のように定義する。

• G(1,d)は大きさ1の石をd個積み上げたものとする。
• G(b,d) (b＞1)は、(d+1)個のG(b-1,d)の間に、計d個大きさbの石を挟むように積み上げたものとする。

G(b,d)を成す石の積み上げを行うとき、下からN段まで積んだ状態だとする。
G(b,d)を積みきるまで必要な石の大きさの総量を求めよ。

解法

G(b,d)の大きさの総量から下部N段分の大きさを引くことを考える。
dは問題中変化しないので定数とみなし、

• H(b) : G(b,d)において積み上げた石の段数
• S(b) : G(b,d)において積み上げた石の大きさの総数

とする。
H(0)=S(0)=0としてH(b) = H(b-1)*(d+1)+d、S(b) = S(b-1)*(d+1) + b*dとなる。

Sの値を式変形するととなるので、G(b,d)の大きさの総量はわかる。
下位N段分の大きさは良くあるフラクタル構造を活かした再帰をして総数を求めよう。
H(b)はH(b-1)の倍以上なので、N段は少なくともH(30)段より小さいため、その範囲で再帰すればよい。

ll N,B,D;
ll H[35],num[35];
ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(ll B,ll N) {
	if(N==0) return 0;
	ll ret=0;
	if(N>H[B-1]) {
		ret+=(N/(H[B-1]+1))*(B+num[B-1]);
		N%=(H[B-1]+1);
	}
	return (ret+hoge(B-1,N))%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B>>D;
	
	ll tot=((modpow(D+1,B+1)+mo-1)*modpow(D)%mo+mo-(B+1))%mo;
	
	for(B=1;B<=32;B++) {
		if(H[B-1]>1<<30) break;
		H[B]=H[B-1]*(D+1)+D;
		num[B]=(B*D+num[B-1]*(D+1))%mo;
	}
	
	cout<<(tot+mo-hoge(B,N))%mo<<endl;
	
}

まとめ

Editorialえらく気合が入ってるな…。