原题链接
考察:贪心
思路:
  每\(k-1\)个间隔放,有多就从前往后放.有一些坑点要注意:

1. \(n%k\)的位置和间隔的位置可以放置\(m\)个,这时需要特判\(res\)的初始值.
2. 不能直接用左移运算符算加倍的结果....

Code

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int M = 1000000009;
int n,m,k;
int qsm(int a,int k,int m)
{
	int res = 1;
	while(k)
	{
		if(k&1) res = (LL)res*a%m;
		a = (LL)a*a%m;
		k>>=1;
	}
	return res;
}
LL solve()
{
	if(m<=(LL)(n+1)/k*(k-1)) return m;
	int cnt = n/k;
	LL res =min(n%k,m-cnt*(k-1));//n多余的位置可能可以放得下m 
	int t = m-cnt*(k-1)-res;//不能更改t,因为res是错的 
	int p = (qsm(2,t+1,M)-2+M)%M;
	res = (res+(LL)p*k%M)%M;//填补后的加倍分数
	res += (LL)(cnt-t)*(k-1)%M;
	res %= M;
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	printf("%lld\n",solve());
	return 0;
}