[BaekJoon]2407コンビ


1.  質問リンク


https://www.acmicpc.net/problem/2407

2.  質問する



サマリ

  • nとmが与えられたとき,n cmの組合せの値は問題であった.
  • 入力
  • :第1行nおよびm、各n、mは5以上、100以下.
  • 出力:n cmの値を出力します.
  • 3.  ソースコード

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.math.BigInteger;
    import java.util.StringTokenizer;
    
    
    public class Main {
    	public BigInteger getCombination(int n, int m) {
    		BigInteger num1 = BigInteger.ONE; // 1
    		BigInteger num2 = BigInteger.ONE; // 1
    		for(int i = 0; i < m; i++) {
    			num1 = num1.multiply(new BigInteger(String.valueOf(n - i))); // BigInteger의 곱셈
    			num2 = num2.multiply(new BigInteger(String.valueOf(i + 1))); // BigInteger의 곱셈
    		}
    		BigInteger result = num1.divide(num2); // BigInteger의 나눗셈
    		return result;
    	}
    	
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            String input = br.readLine();
            br.close();
            StringTokenizer st = new StringTokenizer(input);
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            Main main = new Main();
            bw.write(main.getCombination(n, m) + "\n");
            bw.flush();
            bw.close();
        }
    }

    4.  に近づく

  • の組合せを解く過程で、複数の乗数が生成され、これらの乗数の範囲はIntegerの範囲を超えているため、Integerを用いて組合せの値を求めることはできない.
  • したがって
  • は文字列形式で構成され、数値範囲が無限のBigIntegerを用いて組合せの値を求める.
  • nCr = n!/(n-r)!r!
  • ビット式を用いて分子と分母を計算した.上記のコードで計算する場合(n-r)!分子と分母を簡略化し,次いで分子と分母の計算を行った.
  • BigInteger.「乗算」を使用してBigIntegerの乗算を行い、BigIntegerを初期化するときにStringをパラメータ値に渡す必要があるため、乗算する値はStringに変更され、BigIntegerのパラメータ値に渡されます.
  • 分子と分母の積を求めると、BigInteger.divide(BigInteger)を用いて分子と分母の除算を行い,この値を出力した.