UESTC 1721 吴神,人类的希望(组合计数)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：将n个物品放到m个相同的盒子里，每个盒子至少k个物品的种类
http://acm.uestc.edu.cn/problem.php?pid=1721
最近被虐爆了，来一发水题。
枚举m，然后先给每个盒子放k个，对于剩下的n-m*k个物品放入到m个盒子里，可以为空
dp[i][j]表示把i个物品放到j个盒子里的种类，不能为空，只要加入m个物品，保证至少一个就行了
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define maxn 200005#define eps 1e-8#define inf 1<<30#define LL long long#define zero(a) fabs(a)<eps#define MOD 1000000007using namespace std;int c[1005][1005]={0};void Init(){for(int i=0;i<=1000;i++){c[i][0]=0;c[i][1]=1;c[i][i]=1;for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-j][j])%MOD;}}int main(){int t,n,k;Init();scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);int ans=0;for(int m=1;m<=n/k;m++)ans=(ans+c[n-m*k+m][m])%MOD;printf("%d\n",ans);}return 0;}