题目链接： 

题解链接：

 

代码：

#include 
     
      #define MAX 1000000+100#define MOD 1000000007using namespace std;/*zoj 3747  dp 递推  */typedef long long ll;int n,m,k; ll dp[MAX][3];//dp[i][0]:表示第 i 个位置 放 0 （G士兵） 的方法数目，一直放满 N 个位置 ll solve(int u,int v){  //初始化  dp[0][0] = dp[0][1] = 0;  dp[0][2] = 1;  ll sum = 0;  for (int i=1;i<=n;++i)   {        sum = ( dp[i-1][0] + dp[i-1][1] + dp[i-1][2] )%MOD;        dp[i][2] = sum;        // 对于G士兵         if ( i <= u)          dp[i][0] = sum;        else if ( i == u +1) dp[i][0] = sum-1;        else dp[i][0] = (sum - dp[i-u-1][1] - dp[i-u-1][2] ) % MOD;        //对于R士兵      if ( i <= v)          dp[i][1] = sum;        else if ( i == v +1) dp[i][1] = sum-1;        else dp[i][1] = ( sum - dp[i-v-1][0] - dp[i-v-1][2] ) % MOD;   }    return  ( ( dp[n][0] + dp[n][1] + dp[n][2] ) % MOD ); }int main (){  while(~scanf("%d%d%d",&n,&m,&k))  {    ll ans = solve(n,k);    cout << ( ( (ans - solve(m-1,k))%MOD +MOD ) % MOD) << endl;  }    return 0;}