1819.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include <stdio.h>
#include <string.h>

const int MAXL=50;

struct Num 
{
  int l;
  int d[MAXL];
};

void prnum(Num &p)
{
  int i;

  printf("%d",p.d[p.l]);
  for(i=p.l-1;i>=0;i--) printf("%.4d",p.d[i]);
  printf("\n");
}

void cpynum(Num &a,Num &b)
{
  a.l=b.l;
  memcpy(a.d,b.d,sizeof(int)*(a.l+1));
}

void setnum(Num &p,int x)
{
  p.d[p.l=0]=x;
}

bool iszero(Num &p)
{
  return (p.l==0 && p.d[0]==0);
}

//a+b=c
void add(Num &a,Num &b,Num &c)
{
  int i,w=0;

  if(a.l>b.l) c.l=a.l; else c.l=b.l;
  for(i=0;i<=c.l;i++) {
    c.d[i]=w;
    if(i<=a.l) c.d[i]+=a.d[i];
    if(i<=b.l) c.d[i]+=b.d[i];
    w=c.d[i]/10000,c.d[i]%=10000;
  }
  if(w>0) c.d[++c.l]=w;
}

//a+=b
void add(Num &a,Num &b)
{
  int i,w=0;
  
  for(i=0;i<=a.l || i<=b.l;i++) {
    if(i>b.l && w==0) break;
    if(i>a.l) a.d[++a.l]=0;
    a.d[i]+=w;
    if(i<=b.l) a.d[i]+=b.d[i];
    w=a.d[i]/10000,a.d[i]%=10000;
  }
  if(w>0) a.d[++a.l]=w;
}

//a-=b && a>=b;
void sub(Num &a,Num &b)
{
  int i;

  for(i=0;i<=a.l;i++) {
    if(i>b.l && a.d[i]>=0) break;
    if(i<=b.l) a.d[i]-=b.d[i];
    if(a.d[i]<0) a.d[i]+=10000,a.d[i+1]--;
  }
  while(a.l>0 && a.d[a.l]==0) a.l--;
}

//a*=smallint(x) (x>=0)
void mul(Num &a,int x)
{
  int w=0;
  int i;

  if(x==0) {
    setnum(a,0);
    return;
  }
  for(i=0;i<=a.l;i++) {
    a.d[i]=a.d[i]*x+w;
    w=a.d[i]/10000,a.d[i]%=10000;
  }
  if(w>0) a.d[++a.l]=w;
}
Num opt[51][51];
Num ans[51];
int main()
{
	int i,j,k;	
	for(i=1;i<=50;i++)
	{
		for(j=1;j<=i;j++)
		{
			if(j==1){setnum(opt[i][1],1);setnum(ans[i],1);}
			else
			{
				if(j!=i)
				{
					cpynum(opt[i][j],opt[i-1][j]);
					mul(opt[i][j],j);
				}
				else
				{
					setnum(opt[i][j],0);
				}
				add(opt[i][j],opt[i-1][j-1]);
				add(ans[i],opt[i][j]);
			}
		}

	}
	int n;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		printf("%d ",n);
		prnum(ans[n]);
	}
	return 0;
}