Description
每到端午,beap总要和父母一起包粽子,经过两年的ACM训练,beap总会突发奇想,自己想出一些题目来。因此当他准备把包好粽子放到盘子里的时候,他突然回忆起一个很经典的题目:n个相同的粽子放到m个相同的盘子里(允许盘子为空),有多少种方法呢?(也就是说1,2,1与1,1,2是属于相同的放法)
由于上次遇到这个经典问题都不知道是什么时候,beap已经不知道该如何来解决这个问题,希望你能编写一个程序,替他算出来。
Input
多组测试数据
每组测试数据包含两个整数n,m(0 < n,m <= 100),n代表粽子的个数,m代表盘子的个数。
Output
对于每个n,m,输出答案%1000007。
Sample Input
1 1
2 2
Sample Output
1
2
#include<stdio.h> #define MOD 1000007 int ans[101][101][101]={0},n,m,i,j,dp[101][101]; int main() { for(n=1;n<=100;n++) for(m=1;m<=100;m++) { dp[n][m]=0; if(m==1||n==1) { ans[n][m][m]=1; dp[n][m]=1;continue; } for(j=0;j<=m/n;j++) { for(i=j;i<=m/(n-1);i++) ans[n][m][j]=(ans[n][m][j]+ans[n-1][m-j][i])%MOD; dp[n][m]=(dp[n][m]+ans[n][m][j])%MOD; }//printf("%d,%d:%d ",n,m,dp[n][m]); } while(scanf("%d%d",&m,&n)>0) { printf("%d\n",dp[n][m]); } }