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