hdu 1133 Buy the Ticket

首先，记50的为0，100的为1.

当m=4,n=3时，其中的非法序列有0110010;

从不合法的1后面开始，0->1,1->0,得到序列式0111101

也就是说，非法序列变为了n-1个0,m+1个1.

总的数目=C(m+n,n),非法的=C(m+n,m+1)

符合数目=(C(m+n,n)-C(m+n,m+1))*m!*n!;

化简得：(m+n)!*(m+1-n)/(m+1).

Java代码：

 import java.io.*;

 import java.math.*;

 import java.math.BigInteger;

 import java.lang.String.*;

 import java.util.*;

 public class Main

 {

     public static BigInteger [] p;

     public static void main(String arg[])

     {

         int i;

         p = new BigInteger[201];

         p[0]=BigInteger.valueOf(1);

         for(i=1;i<=200;i++)

             p[i]=p[i-1].multiply(BigInteger.valueOf(i));

         Scanner cin = new Scanner(System.in);

         int k=1;

         while(true)

         {

             int m = cin.nextInt();

             int n = cin.nextInt();

             if(m==0&&n==0) break; System.out.println("Test #"+k+++":");

             if(m<n)

                 System.out.println("0");

             else

                 System.out.println(p[m+n].multiply(BigInteger.valueOf(m+1-n)).divide(BigInteger.valueOf(m+1)).toString());

         }

     }

 }

巴特西

hdu 1133 Buy the Ticket

最新文章

热门文章