Problem's Link:

Mean:

将N分为D份，每份不超过X，有多少种分法？

analyse:

首先我们想到的是迭代，但是数据太大，一路迭代下去必定爆栈+超内存+TLE。

我们枚举X，对于满足条件的X，求和统计答案，不满足条件的X，更新往下迭代的P值。最后对P求和即为答案。

这题DP也可以做，不过上面的方法从时间和空间上都大大优于DP。

Time complexity: O(N)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-16-16.39
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using
namespace
std; 
const
LL
mod
=
1000000007; 
LL
inv
[
5000
];
LL N 
,
X
,
D; 
void
pre() 
{ 
inv
[
1
]
=
1; 
for( 
int
i
=
2; 
i
<
5000; 
i
++) 
inv
[
i
]
= ( 
mod
-
mod
/
i) 
*
inv
[
mod
%
i
]
%
mod; 
}
int
main() 
{ 
pre(); 
while( 
scanf( 
"%d %lld %d"
,
&N 
,
&
D
,
&
X) 
&& N) 
{ 
LL
ans
=
0; 
for( 
int
i
=
0; 
i
*
X
<=N; 
i
++) 
{ 
LL p 
=
1; 
if( 
i
<=
D) 
{ 
for( 
int
j
=
1; 
j
<=
i; 
j
++) 
{ 
                              p 
= ( 
D
-
j
+
1) 
%
mod
* p 
%
mod; 
                              p 
= p 
*
inv
[
j
]
%
mod; 
}
}
else p 
=
0; 
for( 
int
j
=
0; 
j
<
i; 
j
++) p 
= ( 
mod
- p); 
int
gap
= N 
-
i
*
X; 
for( 
int
j
=
1; 
j
<=
gap; 
j
++) 
{ 
                        p 
= ( 
D
+
gap
-
j
+
mod) 
%
mod
* p 
%
mod; 
                        p 
= p 
*
inv
[
j
]
%
mod; 
}
ans
=
ans
+ p; 
if( 
ans
>=
mod) 
ans
-=
mod; 
}
printf( 
"%lld
\n
"
,
ans); 
}
return
0; 
}