#include <cstdio>
int i,j,m,n,t;
long long f[6000][6000];
inline int min(int a,int b){
return a<b?a:b;
}
int main(){
// freopen("ticket.in","r",stdin);
// freopen("ticket.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) f[i][0]=1;
for(i=1;i<=n;++i){
t=min(m,i);
for(j=1;j<=t;++j){
if(i==j){
f[i][j]=f[i][j-1];
}else{
f[i][j]=f[i][j-1]+f[i-1][j];
}
}
}
printf("%lld\n",f[n][m]);
return 0;
}
恩简单的代码。。。没有高精度会爆精度。。再修改+推导吧。
Update:由于找规律。。发个找规律代码
#include <cstdio>
int i,j,m,n,t;
long long f[6000][6000];
inline int min(int a,int b){
return a<b?a:b;
}
int main(){
// freopen("ticket.in","r",stdin);
// freopen("ticket.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) f[i][0]=1;
for(i=1;i<=n;++i){
t=min(m,i);
for(j=1;j<=t;++j){
f[i][j]=f[i][j-1]+f[i-1][j];// 由于当j>i是f[i][j]=0那么也就没问题啦这么写
printf("%d\t",f[i][j]);
}
putchar('\n');
}
printf("%lld\n",f[n][m]);
return 0;
}
恩然后输出。。
1
2 2
3 5 5
4 9 14 14
5 14 28 42 42
6 20 48 90 132 132
7 27 75 165 297 429 429
8 35 110 275 572 1001 1430
9 44 154 429 1001 2002 3432
10 54 208 637 1638 3640 7072
恩第一列是$x$.第二列是$\frac{x(x+1)}{2}-1$,第三列由于是第二列的前缀和