c++ - How do I add this condition in this and make it optimal? -

the question link is: http://codeforces.com/problemset/problem/431/c

quite creative student lesha had lecture on trees. after lecture lesha inspired , came tree of own called k-tree.

a k-tree infinite rooted tree where:

• each vertex has k children;
• each edge has weight;
• if @ edges goes vertex children (exactly k edges), weights equal 1, 2, 3, ..., k.

the picture below shows part of 3-tree.

as dima, friend of lesha, found out tree, wondered: "how many paths of total weight n (the sum of weights of edges in path) there, starting root of k-tree , containing @ least 1 edge of weight @ least d?". dima find answer question. number of ways can rather large, print modulo 1000000007 (10^9 + 7). (open question link above picture of mentioned tree)

input
single line contains 3 space-separated integers: n, k , d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).

output
print single integer — answer problem modulo 1000000007 (10^9 + 7).

so, tried develop recursive solution same. however, not able add constraint make sure edge of weight atleast d should present. how can that? here recursive function:

void calc(int present, int total,int k) // here, present initialised 0.                                         // total equal n reqd.                                         // k value in question {     if (total == present)     {         ans++;         ans = ans%val;         return;     }     else     {         ( int = 1; <= k; i++ )         {             if (present+i <= total)                 return calc(present+i,total,k);         }     } } 

just add following arguments function - d , whether have achieved constraint 1 of these edges @ least d.

void calc(int present, int total,int k, int d, bool atleastd) { 

change constraint increment if atleastd.

    if (total == present && atleastd)     {         ans++;         ans = ans%val;         return;     }     else     {         ( int = 1; <= k; i++ )         {             if (present+i <= total) 

when recursively call function, pass whether atleastd has been achieved before, or if have satisfied constraint (i >= d).

                calc(present+i,total,k,d,atleastd || >= d); 

in addition, removed return in previous line. otherwise, code test 1 possible path - path weights == 1.

        }     } } 

i assume ans , val globals, ans answer problem, initialized 0, , val modulo = 1000000007.

---

finally, while solution might solve small test cases, n <= 15, slow n = 100.

to solve n = 100, suggest learn memoization , dynamic programming. leave exercise you.