下沙的沙子有几粒？

  
  

   
   1 1
3 1
  
  

  
  

   
   1
3
  
  
  
  


  
  

其实与买票问题是相同的思想。买票问题的链接：http://www.voidcn.com/article/p-rvfhcuaa-bkm.html。

不过这里没有全排的问题，所以总的公式是(m+n)!/(m!*n!*(m+1))，化简之后可以得到以下三种情况：

1、当n>1时，为（m+2)*....*(m+n)*(m-n+1)/n!

2、当n=1时，为(m-n+1)

3、当n=0时，为1。

这部分，加入了大数除法的函数。上一次偷懒不想写，这一次由于除数是一个大数，不得不写啦。

参考代码：

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

#define M 10000
char str[M];
//算100以内的阶乘，存放在fact里面
char fact[41][M];

//用字符串表示大数，以'#'号结尾
//str1和str2是乘数，str是结果
int Mutiply(char *str1,char *str2,char *str)
{
	int i,j;
	int a,b;
	int Result[M];
	memset(Result,sizeof(Result));

	for(i = 0; str1[i] != '#'; ++i)
	{
		a = (int)(str1[i] - '0');
		for(j = 0; str2[j] != '#'; ++j)
		{
			b = (int)(str2[j] - '0');
			Result[i + j] += a * b;
		}
	}

	j += i - 1;
	i = 0;

	//到了最高位，如果不为零，就一直赋值。
	for(i = 0; (i < j || Result[i] > 0); ++i)
	{
		str[i] = Result[i] % 10 + '0';
		Result[i+1] += Result[i] / 10;
	}

	str[i] = '#';//加结束标志
	return i;
}

//除法的str1从0-n依次是高位到地位。故得到的str的结果也是一致的
int Divide(char *str1,int b,char* str)
{
	int i;
	int j;
	int carry = 0;
	int flag = 0;

	for(i = 0,j = 0; str1[i] != '#'; ++i)
	{
		carry = (str1[i] - '0') + carry * 10; 
		if(carry < b)
		{
			if(flag)
			{
				str[j++] = '0';
			}
			continue;
		}
		else
		{
			str[j++] = carry / b + '0';
			carry %= b;
			flag = 1;
		}
	}
	str[j] = '#';
	str[j + 1] = 0;
	return j;
}


//nLen表示所有字符的个数
void Invert(char *str,int nLen)
{
	int i;
	char temp;

	for(i = 0; i < (nLen >> 1); ++i)
	{
		temp = str[i];
		str[i] = str[nLen - i - 1];
		str[nLen - i - 1] = temp;
	}
}

void Print(char *str,int nLen)
{
	int i;
	for(i = 0; i < nLen; ++i)
	{
		putchar(str[i]);
	}
	printf("n");
}



int Fact(int a)
{
	char buf[15];
	int nLen;
	fact[0][0] = '0';
	fact[1][0] = '1';
	fact[1][1]= '#';//记得加结束标志
	for(int i = 2; i <= a; ++i)
	{
		itoa(i,buf,10);
		nLen = strlen(buf);
		buf[nLen] = '#';//记得加结束标志
		buf[nLen + 1] = 0;
		Invert(buf,nLen);
		nLen = Mutiply(fact[i - 1],fact[i]);
		fact[i][nLen] = '#';//记得加结束标志
	}
	return nLen;
}

void main()
{
	int m,n;
	char buf[5];
	int i;
	int nLen;

	while(scanf("%d %d",&m,&n) != EOF)
	{
		if(n > m)
		{
			printf("0n");
			continue;
		}
		else if(n == 0)
		{
			printf("1n");
			continue;
		}

		itoa(m - n + 1,fact[m + 1],10);//先把要成的(m-n+1)的因子放在fact[m+1]中
		nLen = strlen(fact[m + 1]);
		fact[m + 1][nLen] = '#';//记得加结束标志
		fact[m + 1][nLen + 1] = 0;
		Invert(fact[m + 1],nLen);

		for(i = 2; i <= n; ++i)
		{
			itoa(m + i,10);
			nLen = strlen(buf);
			buf[nLen] = '#';//记得加结束标志
			buf[nLen + 1] = 0;
			Invert(buf,nLen);
			nLen = Mutiply(fact[m + i - 1],fact[m + i]);
			fact[i][nLen] = '#';//记得加结束标志
		}

		Invert(fact[m + n],nLen);//先反转之后再除

		for(i = 2; i <= n; ++i)
		{
			nLen = Divide(fact[m + n],i,str);
			memcpy(fact[m+n],str,(nLen + 2) * sizeof(char));
		}

		Print(fact[m+n],nLen);
	}
}