joj2443

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]