UVa 10943 - How Do You Add?(组合数)

求一个数n拆成k个数的方法个数。
利用隔板法求得

a n s = ( n + k − 1 k − 1 )

利用 c [ i ] [ j ] = ( c [ i − 1 ] [ j ] + c [ i − 1 ]
[ j − 1 ] ) % m o d 递推预处理组合数,然后读入 n 、 k 输出答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
const int maxn=210;
const int mod=1000000;
int c[maxn][maxn];
int main(){
for(int i=0;i<maxn;++i) c[i][0]=1;
for(int i=1;i<maxn;++i)
for(int j=1;j<=i;++j)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
int n,k;
while(~scanf("%d%d",&n,&k)&&(n||k))
printf("%d\n",c[n+k-1][k-1]);
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。