1 /************************************************************ 2  * Author : darkdream 3  * Email : darkdream1994@gmail.com  4  * Last modified : 2014-08-02 14:28 5  * Filename : 431c.cpp 6  * Description : 7  * *********************************************************/ 8 // File Name: 431c.cpp 9 // Author: darkdream10 // Created Time: 2014年08月01日 星期五 20时22分33秒11 12 #include<vector>13 #include<list>14 #include<map>15 #include<set>16 #include<deque>17 #include<stack>18 #include<bitset>19 #include<algorithm>20 #include<functional>21 #include<numeric>22 #include<utility>23 #include<sstream>24 #include<iostream>25 #include<iomanip>26 #include<cstdio>27 #include<cmath>28 #include<cstdlib>29 #include<cstring>30 #include<ctime>31 32 #define LL long long33 using namespace std;34 LL dp[104][104]; 35 LL dpa[104][104];36 #define md 100000000737 int main(){38     int n , k , d; 39     scanf("%d %d %d",&n,&k,&d);40     memset(dp,0,sizeof(dp));41     memset(dpa,0,sizeof(dpa));42     dp[0][0] = 1; 43     LL ans = 0 ;44     for(int i = 1;i <= n;i ++)45     {46         for(int j = i-1;j <= n;j ++)47         {48            if(dp[i-1][j]) 49            {50               for(int s = 1;s <= k ; s ++)51               {52                  if(j + s > n)53                      break;54                  if(s <  d )55                      dp[i][j+s] = (dp[i][j+s] + dp[i-1][j]) % md;56                  else 57                      dpa[i][j+s] = (dpa[i][j+s] + dp[i-1][j]) % md;58               }59            }60            if(dpa[i-1][j])61            {62               for(int s = 1; s <= k; s++)63               {64                  if(j + s > n)65                      break;66                  dpa[i][j+s] = (dpa[i-1][j]+ dpa[i][j+s]) %md;67               }68            }69         }70     }71     for(int i = 1;i <= n;i ++)72         ans =( dpa[i][n]+ ans)%md;73     printf("%I64d\n",ans%md);74 return 0;75 }