uestc 1721 吴神,人类的希望

// 将n个相同的球放进m个盒子 盒子不为空的方法总数
// dp[i][j] 表示i个盒子 j个球的方法总数
// 递推关系 dp[i][j]=dp[i-1][j-1]+d[i][j-i]
// a. i-1个盒子放j-1个球 第j个球放进第i个盒子中
// b. i个盒子放了j-i个球 再放进i个球 每个盒子放一个
// 注意 ans=ans+dp[i][n-k*i+i] 这里的 n-k*i+i 
// 加 i 的目的是为了 n-k*i+i>=i 这样就得到盒子不为空计数

 
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 1000010
#define maxm 1000010
#define LL long long
int dp[1010][1010];
int main(){
    int i,j;
    dp[0][0]=1;// dp[i][0]=0;
    for(i=1;i<=1000;i++)
    {
        dp[i][i]=1;
        for(j=i+1;j<=1000;j++)
         dp[i][j]=(dp[i-1][j-1]+dp[i][j-i])%MOD;
    }
   // for(i=1;i<=1000;i++)
     // printf("%d ",dp[i][i]);
    int T;
    scanf("%d",&T);
    int m,n,k;
    while(T--){
        scanf("%d %d",&n,&k);
        m=n/k;
        int ans=0;
        for(int i=1;i<=m;i++){
            ans=(ans+dp[i][n-k*i+i])%MOD;
        }
        printf("%d
",ans);
    }
}