hdu 1133

看了别人的思路才找到怎么写的……

#include "stdio.h"
#include "string.h"

int fib[210][400];
int len=1;

void cal_fib(int n)
{
 int i,j;
 int carry=0;

 memset(fib,0,sizeof(fib));

 fib[0][0]=1;
 fib[1][0]=1;
 len=1;
 for(i=2;i<=n;i++)
 {
  carry=0;
  for(j=0;j<len;j++)
  {
   fib[i][j]=fib[i-1][j]*i+carry;
   if(fib[i][j]>=10)
   {
    carry=fib[i][j]/10;
    fib[i][j]=fib[i][j]%10;
   }
   else
    carry=0;
   //printf("1:%d carry:%d ",fib[i][j],carry);
  }
  while(carry!=0)
  {
   fib[i][len++]=carry%10;
   carry=carry/10;
   //printf("1:%d ",fib[i][j]);
  }
  //printf("\nlen:%d\n",len);
 }
}

int main()
{
 int m,n;
 int s[401];
 int carry,borrow,i,j,k,t;
 int count=1;

 //cal_fib();

 while(scanf("%d%d",&m,&n)==2)
 {
  if(m==0&&n==0)
   break;
  if(n>m)
  {
   printf("Test #%d:\n",count++);
   printf("0\n");
   continue;
  }
  len=1;
  cal_fib(m+n);
  //printf("\nmain->len:%d\n",len);
  k=m+1-n;
  carry=0;

  /*for(i=len-1;i>=0;i--)
   printf("%d",fib[m+n][i]);
  printf("\n");*/

  memset(s,0,sizeof(s));

  //printf("\n*len:%d\n",len);
  for(i=0;i<len;i++)
  {
   s[i]=fib[m+n][i]*k+carry;
   if(s[i]>=10)
   {
    carry=s[i]/10;
    s[i]=s[i]%10;
   }
   else
    carry=0;
   //printf("%d",s[i]);
  }
  while(carry)
  {
   s[len++]=carry%10;
   carry=carry/10;
  }

  borrow=0;

  for(i=len-1;i>=0;i--)
  {
   t=s[i]+borrow*10;
   borrow=t%(m+1);
   s[i]=t/(m+1);
  }
  printf("Test #%d:\n",count++);
  i=len-1;
  while(!s[i])
   i--;
  for(;i>=0;i--)
   printf("%d",s[i]);
  printf("\n");
 }

 return 0;
}