HDOJ 题目1133Buy the Ticket（大数，数学）
发布时间：2020-12-14 03:04:13 所属栏目：大数据 来源：网络整理
导读：Buy the Ticket Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4606????Accepted Submission(s): 1949 Problem Description The "Harry Potter and the Goblet of Fire" will be on show in t
Buy the TicketTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4606????Accepted Submission(s): 1949
Problem Description
The "Harry Potter and the Goblet of Fire" will be on show in the next few days. As a crazy fan of Harry Potter,you will go to the cinema and have the first sight,won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill). Now the problem for you is to calculate the number of different ways of the queue that the buying process won't be stopped from the first person till the last person. Note: initially the ticket-office has no money. The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
?
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise,m,n <=100.
?
Output
For each test case,first print the test number (counting from 1) in one line,then output the number of different ways in another line.
?
Sample Input
?
Sample Output
?
Author
HUANG,Ninghai
?
Recommend
Eddy???|???We have carefully selected several similar problems for you:??
1267?
1297?
1134?
1023?
1143?
?
推導過程如下：
m個人拿50，n個人拿100
1、如果n> m，那麼排序方法數為0，這一點很容易想清楚
2、現在我們假設拿50的人用‘0’表示，拿100的人用‘1’表示。
如果有這麼一個序列0101101001001111。
當第K個位置出現1的個數多餘0的個數時就是一個不合法的序列了
假設m=4,n=3的一個序列是：0110100。顯然，它不合法，現在我們把它稍微變化一下：
把第二個1（這個1前面的都是合法的）後面的所有位0變成1，1變成0.
#include<stdio.h>
#include<string.h>
int fact[200][200],res[10000];
void muti(int a[],int b)
{
int i,temp=0;
for(i=100;i>=0;i--)
{
temp+=a[i]*b;
a[i]=temp%10000;
temp/=10000;
}
}
void fun()
{
int i;
fact[0][100]=fact[1][100]=1;
for(i=2;i<=200;i++)
{
memcpy(fact[i],fact[i-1],101*sizeof(int));
muti(fact[i],i);
}
}
void div(int a[],temp=0;
for(i=0;i<=100;i++)
{
temp=temp*10000+a[i];
a[i]=temp/b;
temp%=b;
}
}
int main()
{
int n,c=0;
fun();
while(scanf("%d%d",&m,&n)!=EOF,n||m)
{
int j,i;
printf("Test #%d:n",++c);
if(n>m)
{
printf("0n");
continue;
}
memcpy(res,fact[m+n],101*sizeof(int));
muti(res,m-n+1);
div(res,m+1);
/* for(i=0;i<=100;i++)
if(res[i])
break;
printf("%d",res[i++]);
while(i<=100)
printf("%d",res[i++]);
printf("n");*/
i=0;
while(res[i]==0 && i<101) i++;
printf ( "%d",res[i++] );
while(i<101)
{
printf ( "%04d",res[i++] );
}
printf("n");
}
}
就得到0111011這個序列1的數量多餘0的數量，顯然不合法，但現在的關鍵不是看這個序列是不是合法的
關鍵是：他和我們的不合法序列0110100成一一對應的關係。
也就是說任意一個不合法序列（m個0，n個1），都可以由另外一個序列（n-1個0和m+1個1）得到。
另外我們知道，一个序列要麼是合法的，要麼是不合法的
所以，合法序列數量= 序列總數量 - 不合法序列的總量
序列總數可以這樣計算m+n個位置中，選擇n個位置出來填上1，所以是C(m+n,n).
不合法序列的數量就是：m+n個位置中，選擇m+1個位置出來填上1，所以是C(m+n,m+1).
然後每個人都是不一樣的，所以需要全排列m!* n!.
所以最後的公式為：(C(m+n,n)- C(m+n,m+1)) * m! * n!
化簡即為：(m+n)!*(m-n+1)/(m+1)
ac代码 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |