卡特兰数变形 HDU1133

 1 import java.math.*;
 2 import java.util.*;
 3 
 4 public class Main
 5 {
 6     public static void main(String[] args)
 7     {
 8         int m,n;
 9         int num=1;
10         Scanner cin=new Scanner (System.in);
11         while(cin.hasNext())
12         {
13             int flag=1;
14             BigInteger ans1=BigInteger.ONE;
15             BigInteger ans2=BigInteger.ONE;
16             m=cin.nextInt();
17             n=cin.nextInt();
18             if(m<n)
19             {
20                 ans1=BigInteger.ZERO;
21                 flag=0;
22             }
23             if(m==0&&n==0)
24                 break;
25             if(flag==1)
26             {
27                 for(int i=m+1;i<=n+m;i++)
28                 {
29                     ans1=ans1.multiply(BigInteger.valueOf(i));
30                 }
31                 for(int i=1;i<=n;i++)
32                 {
33                     ans1=ans1.divide(BigInteger.valueOf(i));
34                 }
35                 for(int i=m+2;i<=n+m;i++)
36                 {
37                     ans2=ans2.multiply(BigInteger.valueOf(i));
38                 }
39                 for(int i=1;i<=n-1;i++)
40                 {
41                     ans2=ans2.divide(BigInteger.valueOf(i));
42                 }
43                 ans1=ans1.subtract(ans2);
44                 if(ans1.compareTo(BigInteger.ZERO)==0)
45                     ans1=BigInteger.ONE;
46                 for(int i=1;i<=m;i++)
47                 {
48                     ans1=ans1.multiply(BigInteger.valueOf(i));
49                 }
50                 for(int i=1;i<=n;i++)
51                 {
52                     ans1=ans1.multiply(BigInteger.valueOf(i));
53                 }
54             }
55             System.out.println("Test #"+num+":");
56             num++;
57             System.out.println(ans1);
58         }
59     }
60 }
View Code
{C(N+M,N)-C(N+M.N+1)}*A(N,N)*A(M,M)