Codeforces 338A Quiz

問題

n問のクイズをやって、ちょうどm問正解した。
このクイズは正解すると1問につき1点で、
k回連続で正解すると、(1点が加えられた後で)現在の得点が倍になる。
(その後、連続正解数のカウントは0に戻る)


得られた得点の最小値を求め、mod 10^9+9で出力せよ。

制約条件

n, m, k≦10^9

方針

まず、倍になる回数を最小化するのがよい。
同じ回数なら、倍になるのができるだけ最初に偏っているほうがよい。
なのでそのような並びでの得点を考える。


そのような並びは、
○○...○○×○○○○×○○○○×○○○○×○○○○
みたいな感じ。k = 5として。

×の個数をxとすると、(x+1) * (k-1)がm以上だったら倍はなし。
そうでなかったら、最初の部分のm - x*(k-1)個の連続する部分にだけ○がある。
ここでの得点を計算すればいい。

ソースコード

ll mod = (int)1e9 + 9;
int n, m, k;
ll pw(ll n, ll m){
	ll res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
ll func(ll m){
	ll n = m / k;
	return m % k + k * (pw(2, n + 1) + mod - 2);
}

int main(){
	cin >> n >> m >> k;
	int x = n - m;
	
	if((k - 1) * (x + 1ll) >= m){
		cout << m << endl;
		return 0;
	}
	ll ans = func(m - (k - 1) * x);
	ans += (k - 1ll) * x;
	cout << ans % mod << endl;
	
	return 0;
}