第4回 ドワンゴからの挑戦状 本戦 : D - ニワンゴくんとゲーム

これ時間があったら思いついてたの…かなぁ？
https://dwacon2018-final-open.contest.atcoder.jp/tasks/dwacon2018_final_d

問題

現在の魔力をXとすると、１ターンで以下のように魔力を変動できる。

• Xを1インクリメントする
• Xを2倍にする
• Xを2倍にして1インクリメントする

初期状態で魔力を1としたとき、最終的な魔力をN[i]にする、というクエリがQ個与えられる。
そのような魔力の値を達成する変動順の組み合わせをそれぞれ答えよ。

解法

f(x)を魔力をxにするための組み合わせとすると、

• f(1) = 1
• f(x) = f(x-1) + f(floor(x/2)) (xが2以上の場合)

f(x)を決めるのにおよそf(floor(x/2))が関係するのであれば、f(floor(x/2))を決めるのにf(floor(x/4))が関係する…
ということで、f(floor(x/2^k))の形の要素をまとめて管理するとうまくいきそうである。

後の処理のためfloorでなくceilで考え、以下のベクトルを考える。
g(x) = (f(x), f(ceil(x/2)), f(ceil(x/4)), .. , f(ceil(x/2^60))

xの2進数におけるtrailing zeroの数をT(x)とする。
g(x+1) = A(x) * g(x)となる行列A(x)を考えると、A(x)はT(x)で定まる。
B(y) := T(x) = yであるようなxに対するA(x) とすると g(x) = B(T(x-1))*B(T(3))*B(T(2))*B(T(1))...*g(1) と置ける。

このBの積はフラクタル状に同じ形状を繰り返すので、うまく行列累乗に似た要領で倍々の長さの積を順次求めることができる。
あとは事前にBの積のパターンを求めておき、クエリに応じてO(log N[i])個掛け合わせればよい。
(実際は行列同士を直接かけるとTLEするので、ベクトルに順次行列を掛けていく。)

int Q;
ll N;

ll mo=1000000007;

const int MAT=64;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat S[64];
Mat A[64];
Mat B[64];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,63) {
		FOR(j,64) {
			S[i].v[j][j]=1;
			if(j<=i) S[i].v[j+1][j]=1;
		}
	}
	A[0]=B[0]=S[0];
	for(i=1;i<=63;i++) {
		A[i]=mulmat(B[i-1],S[i]);
		B[i]=mulmat(A[i],B[i-1]);
	}
	
	cin>>Q;
	while(Q--) {
		
		cin>>N;
		N--;
		
		vector<ll> E(64,1);
		for(i=59;i>=0;i--) if(N&(1LL<<i)) {
			vector<ll> E2(64,0);
			FOR(x,64) FOR(y,64) (E2[x]+=E[y]*A[i].v[y][x])%=mo;
			E=E2;
		}
		cout<<E[0]<<endl;
	}
	
}

解法

CもDもフラクタルか…？