AtCoder Beginner Contest 021 D: 多重ループ (組み合わせ・モジュラ逆数)

問題

D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder

解法

1からnの中から重複を許してk個選ぶという問題に帰着できる。 を求めたいが、割り算をすると計算に時間がかかりすぎる。そこでモジュラ逆数を使う。

モジュラ逆数 - Wikipedia

コード

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static final long MOD = 1000000007;
	public static final BigInteger M_INTEGER = new BigInteger(String.valueOf(MOD));

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		sc.close();

		if (n == 1) {
			System.out.println(1);
			return;
		}

		long[] fact = new long[n - 1];
		long[] modInv = new long[n - 1];
		for (int i = 1; i <= n - 1; i++) {
			if (i == 1) {
				fact[0] = k + 1;
			} else {
				fact[i - 1] = (fact[i - 2] * (k + i)) % MOD;
			}
			BigInteger integer = new BigInteger(String.valueOf(i));
			integer = integer.modInverse(M_INTEGER);
			integer.mod(M_INTEGER);
			modInv[i - 1] = integer.longValue();
		}
		long ans = fact[n - 2];
		for (int i = 0; i < modInv.length; i++) {
			ans *= modInv[i];
			ans %= MOD;
		}
		System.out.println(ans);
	}
}