首页 > 代码库 > hdu1223
hdu1223
n个数,只能用<或者=连接,共有多少种方案。
F[i][j]=(F[i-1][j]+F[i-1][j-1])*j
F[i][j]代表i个数,有j个不同值的情况。比如A<B=C<D,j=3.
大数模板
#include <stdio.h>#include <string.h>const int MAX =505;struct BigNum{ int num[MAX]; int len;} a[51][51];BigNum Add(BigNum &a, BigNum &b){ BigNum c; int i, len; len = (a.len > b.len) ? a.len : b.len; memset(c.num, 0, sizeof(c.num)); for(i = 0; i < len; i++) { c.num[i] += (a.num[i]+b.num[i]); if(c.num[i] >= 10) { c.num[i+1]++; c.num[i] -= 10; } } if(c.num[len]) len++; c.len = len; return c;}BigNum Mul1(BigNum &a, int &b){ BigNum c; int i, len; len = a.len; memset(c.num, 0, sizeof(c.num)); //乘以0,直接返回0 if(b == 0) { c.len = 1; return c; } for(i = 0; i < len; i++) { c.num[i] += (a.num[i]*b); if(c.num[i] >= 10) { c.num[i+1] = c.num[i]/10; c.num[i] %= 10; } } while(c.num[len] > 0) { c.num[len+1] = c.num[len]/10; c.num[len++] %= 10; } c.len = len; return c;}void init(){ int i,j; for(i=0; i<=50; i++) for(j=0; j<=50; j++) if(i<j||j==0) { a[i][j].num[0]=0; a[i][j].len=1; } else if(j==1) { a[i][j].num[0]=1; a[i][j].len=1; } else { a[i][j]=Add(a[i-1][j],a[i-1][j-1]); a[i][j]=Mul1(a[i][j],j); }}int main(){ BigNum sum; int i,p,n; init(); scanf("%d",&p); while(p--) { for(i=0;i<MAX;i++) sum.num[i]=0; sum.len=0; scanf("%d",&n); for(i=1;i<=n;i++) sum=Add(sum,a[n][i]); for(i=sum.len-1;i>=0;i--) printf("%d",sum.num[i]); printf("\n"); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。