Buy the Ticket HDU 1133

时间:2024-10-07 17:04:50

传送门

[http://acm.hdu.edu.cn/showproblem.php?pid=1133]

题目描述和分析

Buy the Ticket HDU 1133

Buy the Ticket HDU 1133

Buy the Ticket HDU 1133

代码

#include<iostream>
#include<string.h>
using namespace std; void Multiply(int a[],int z)//大数a[]和小数z相乘,结果存储在a[]中
{
int maxn = 2000;
int c = 0;
for(int j=maxn-1;j>=0;j--)//用z乘以a[]的每一位
{
int x = a[j] * z + c;
a[j] = x % 10;
c = x / 10;
}
} int main()
{
int m,n,num=0;
while(1)
{
cin >> m >> n;
if(!m && !n)
break; cout << "Test #" << ++num << ":" << endl; if(m<n)//m<n,没有符号条件的排列
{
cout << 0 << endl;
continue;
} const int maxn = 2000;
int a[maxn],i,j;
memset(a,0,sizeof(a));
a[maxn-1] = 1; if(n==0)//此时全是拿50元的人,直接输出m!的结果
for(i=2;i<=m+n;i++)//计算m!
Multiply(a,i); else if(n>=1)//此时按照公式计算,避开除法
{
for(i=2;i<=m+n;i++)
if(i!=m+1)//如果,某一项恰好是分母(m+1),则不乘以这一项
Multiply(a,i); Multiply(a,m-n+1);//根据公式,最后还要乘以(m-n+1)一项
} for(i=0;i<maxn;i++)
if(a[i])//从i开始,非零
break;
for(j=i;j<maxn;j++)//输出
cout << a[j];
cout << endl;
} return 0;
}