hdu1261 JAVA

16826 ワード

タイトル:
1つのAと2つのBは全部で3つの文字列を構成することができる:“ABB”,“BAB”,“BBA”.いくつかのアルファベットとそれらの対応する個数を与えて、合計でいくつの異なる文字列を構成することができるかを計算する.
考え方:
最初はこの問題を見て指数型母関数を感じたが、結局直接水を叩いて、それから水waをして、ああ、SB、それから大体この問題の答えを計算すると数百位に違いない.それから自分で書いて、書いて、いろいろなwaを書いて、それからあきらめて、いっそJAVAの大数を勉強して、前に使ったことがなくて、入出力を入力して、フォーマットを変換して、classなどを一晩中つついて、やっとaになって、苦労しました.
実はこの题目は母の関数を使う必要はなくて、母の関数は何の复雑さを计算して(自分のJAVAは何もできなくて、ちょうど学んだのは母の関数の中で复雑な感じがします)、実は私达は数学の思想を组み合わせてすることができて、N个の异なる数があるならば、彼らが组み合わせることができる个数はNです!しかし、本題では同じ数字が出る可能性があるので、答えは相対的に少ないに違いありません.
私たちはまずこれらの数字が違うと仮定して、Nです!(nはタイトルのnではなく、すべての数字の合計個数sum)を考えて、同じ場合があることを考えて、AAAがあれば、当初は3つの異なる数と見なしていたので、この3つの数の組み合わせ数(1*2*3)で除算すれば元に戻すことができ、すべてがこのように処理され、答えは:
sum:すべての数値と
c[i]:iはいくつありますか
ans =    sum!/(c[1]! * c[2]! * .....*c[n]!);
以下は自分のWAの母関数とAcの組み合わせ数です(Acのこのコードはネットで探していますが、自分は最初はJAVAは何もできませんでしたが、明日はJAVAでよく使うものを書きます)
#include

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
"
,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();
        }
    }
}