SPOJ 12943. Counting， dp ，巧妙

Given integers N and M, output in how many ways you can take N distinct positive integers such that sum of those integers is <= M. Since result can be huge, output it modulo 1000000007 (10^9 + 7)

N <= 20

M <= 100000

Input

First line of input is number t, number of test cases. Each test case consists only of 2 numbers N and M, in that order.

Output

Output number aksed in description.

题意：找n个不同的数且和不超过m, 求有多少种方案？

DP

n个数为ai，bi = an-i+1 - an-i, bn = a1.

sum(a[i]) = sum(b[i]*i)

即把问题

n个不同的数且和不超过m

转化为

b[i]>0 且 sum(b[i]*i)<=m

然后设dp[i][j]表示b数组前i项的和为j的方案数。

则：dp[i][j] = dp[i][j-i] + dp[i-1][j-i];

answer = sum(dp[n][j]);(1<=j<=m)

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">#include using namespace std; const int mod = 1e9 + 7; const int maxn = 20; const int maxm = 1e5; int dp[maxn+10][maxm+10]; int n, m; int main() { int T; dp[0][0] = 1; for(int i=1; i<=maxn; ++i) for(int j=i; j<=maxm; ++j){ dp[i][j] = dp[i][j-i] + dp[i-1][j-i]; if(dp[i][j]>=mod) dp[i][j] -= mod; } scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); int ans = 0; for(int i=1; i<=m; ++i) { ans += dp[n][i]; if(ans>=mod) ans -= mod; } printf("%d\n", ans); } return 0; }