http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1884
题目大意:
把K个不超过N的非负整数加起来,使得他们的和为N,有多少种方法?比如N=5,K=2,有6种方法。即0+5,1+4,2+3,3+2,4+1,5+0.
输入N和K,求方法总数除以10^6的余数
思路:
递推,从(n-1,k)种的解+上1不就是答案了么?同理从(n,k-1)中加上个0不也是答案么,
所以有:ans[i][j]=(ans[i][j-1]+ans[i-1][j])%mod;
OK注意初始化,(1,k)的解为k,我们可以1个1,k-1个0,组成的全排列。而(n,1)为1,只能选自己嘛。
#include<cstdio> const int MAXN=100+10; const int mod=1000000; int ans[MAXN][MAXN]; int main() { for(int i=1;i<=100;i++) { ans[1][i]=i; ans[i][1]=1; } for(int i=2;i<=100;i++) for(int j=2;j<=100;j++) ans[i][j]=(ans[i][j-1]+ans[i-1][j])%mod; int n,k; while(scanf("%d%d",&n,&k),n||k) { printf("%d\n",ans[n][k]); } return 0; }