http://acm.jlu.edu.cn/joj/showproblem.php?pid=2443
我水啊
刚开始想到的方程f[n+1,m] = f[n,m] + f[n,m-1] + … + f[n,m-n];
但是这个方程时间复杂度是O(N^3)。
然后仔细观察，发现f[n+1,m] = f[n,m]+f[n+1,m-1],并且减去f[n,m-n-1];
复杂度是O(N^2)
[code language="cpp"]
void init()
{
memset(f,0,sizeof(f));
f[1][0] = 1;
for(int i=1; i<=1000; i++)
{
int tmp = min(10000,((i+1)*i)/2);
f[i+1][0] = f[i][0];
for(int j = 1; j<= tmp ; j ++)
{
if(j - 1 >= 0)
f[i+1][j] = (f[i][j] + f[i+1][j-1]) % mod;
if(j - i > 0 )
{
f[i+1][j] -= f[i][j-i-1];
if(f[i+1][j] < 0) f[i+1][j] += mod;
}
}
}
}
[/code]