轉載于http://blog.csdn.net/zu_xu/article/details/9401497
采用遞推:當N<M時,必不存在滿足條件的方法,因而結果為0;N=M時,方案數恰好為1。N>M時,若1到N-1滿足條件,則N可以任意染色,方案數為C(N-1)*2;否則,必有1到N-M-1不滿足條件,N-M為藍,N-M+1到N-1為紅,這時将N染成紅色即可,方案數為2^(N-M-1)-C(N-M-1),即1到N-M-1所有的染色方案數減去滿足條件的方案數。
#include <cstdio>
#include <memory.h>
#define mod 1000000007
typedef long long ll;
ll pow2[100000];
ll iter[100001];
int main()
{
int n, m;
*pow2 = 1;
for(int i=1; i<100000; ++i)
pow2[i] = (pow2[i-1]*2)%mod;
while(~scanf("%d%d", &n, &m))
{
if(n < m)
printf("0\n");
else if(n == m)
printf("1\n");
else
{
memset(iter, 0, m*sizeof(ll));
iter[m] = 1;
for(int i=m+1; i<=n; ++i)
iter[i] = (2*iter[i-1]+pow2[i-m-1]-iter[i-m-1]+mod)%mod;
printf("%lld\n", iter[n]);
}
}
return 0;
}