Buy the Ticket

 1 import java.util.*;
 2 import java.math.*;
 3 public class Main
 4 {
 5     public static void main(String []args)
 6     {
 7         Scanner cin=new Scanner(System.in);
 8         int i,n,m;
 9         int count=1;
10         while(cin.hasNext())
11         {    
12             m=cin.nextInt();
13             n=cin.nextInt();
14             if(m==0&&n==0)
15             break;
16             if(m<n)
17             {
18                 System.out.println("Test #"+count+":");
19                 System.out.println(0);
20              }
21              else
22              {
23             BigInteger s1 = BigInteger.valueOf(1);
24             BigInteger s2 = BigInteger.valueOf(1);
25             for(i=1;i<=n+m;i++)
26             {
27                 s1=s1.multiply(BigInteger.valueOf(i));
28             }
29             s1=s1.multiply(BigInteger.valueOf(m+1-n));
30             s1=s1.divide(BigInteger.valueOf(m+1));
31             System.out.println("Test #"+count+":");
32             System.out.println(s1);    
33             }
34             count++;
35         }
36     }
37 }

( C(m+n, n) - C(m+n, m+1) ) * m!* n! 化简即 (m+n)!* (m-n+1) / (m+1)

推导过程如下 :

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

就得到 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)