hdu1261 JAVA

题意:

一个A和两个B一共可以组成三种字符串:"ABB","BAB","BBA".给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.

思路:

刚开始一看这个题目感觉指数型母函数,结果直接水敲,然后水wa了,哎,SB了,后来大体一算这个题目的答案肯定是几百位,然后就自己写啊写啊写,各种wa,后来放弃了,干脆去学JAVA大数,之前没用过,就输入输出,转换格式,class什么的捅咕了一个晚上,终于a了,费劲啊,

其实这个题目没有必要用母函数,母函数计算什么的复杂(自己JAVA什么不会,刚学的结合到母函数里就感觉复杂了) , 其实我们可以用组合数学的思想来做 ,想想假如有N个不同的数,他们能组合的个数是 N!,但是本题中则可能出现相同的数字,所以答案肯定相对较少,

我们先假设这些数字不同,则是 N!(n 不是题目中的n而是所有数字的总个数 sum),然后考虑出现相同的情况, 假如有AAA,当初我们把他们当成三个不同的数,所以只要除以这三个数的组合数(1 * 2 * 3)就能还原回去了,所有的都这么处理,答案则是:

sum : 所有数字个数和

c[i] : i 有多少个

ans = sum! / (c[1]! * c[2]! * .....*c[n]!);

下面是自己的 WA的母函数和 Ac的组合数(Ac的这个代码是在网上找的,自己一开始JAVA什么都不会 ,明天会再写个JAVA 常用的东西)

#include<stdio.h>



double c[30] ,c1[26*12+10] ,c2[26*12+10];

double jcs[15];

void DB_JC()

{

   jcs[0] = 1;

   for(int i = 1 ;i <= 13 ;i ++)

   jcs[i] = jcs[i-1] * i;

}

int main ()

{

   int i ,j ,k ,n ,m;

   while(scanf("%d" ,&n) && n)

   {

      m = 0;

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

      {

         scanf("%lf" ,&c[i]);

         m += int(c[i]);

      }

      for(i = 0 ;i <= m ;i ++)

      c1[i] = c2[i] = 0;

      DB_JC();

      c1[0] = 1.0 / jcs[0];

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

      {

         for(j = 0 ;j <= m ;j ++)

         for(k = 0 ;k + j <= m && k <= c[i] ;k ++)

         c2[k+j] += c1[j]/jcs[k];

         for(j = 0 ;j <= m ;j ++)

         c1[j] = c2[j] ,c2[j] = 0;

      }

       printf("%I64d\n" ,int(c1[m] * jcs[m]));

    }

    return 0;

}

组合数学 Ac JAVA 代码

import java.util.Scanner;

import java.math.BigInteger;

public class Main

{

    public static void main(String args[])

    {

        Scanner cin = new Scanner(System.in);

        BigInteger f1, f2;

        int []s = new int[26];

        int n, sum;

        n = cin.nextInt();

        while (n != 0)

        {

            sum = 0;

            for (int i=0; i<n; ++i)

            {

                s[i] = cin.nextInt();

                sum += s[i];

            }

            f1 = new BigInteger("1");

            for (int i=1; i<=sum; ++i)

            {

                f1 = f1.multiply(BigInteger.valueOf(i));

            }

            f2 = new BigInteger("1");

            for (int i=0; i<n; ++i)

            {

                for (int j=1; j<=s[i]; ++j)

                {

                    f2 = f2.multiply(BigInteger.valueOf(j));

                }

            }

            System.out.println(""+f1.divide(f2));

            n = cin.nextInt();

        }

    }

}

巴特西

hdu1261 JAVA

最新文章

热门文章