逆元を使って組み合わせの数を求める

AtCoderのABC145、D問題です。
atcoder.jp

組み合わせの数は、nCkで求められます。
ただ、そのまま計算すると、n!/(n-k)!*k!となり、分母、分子ともに数値が大きくなります。
ここでは、modで割ったものを答えとするので、逆元を使って計算量をlog(mod)に抑えつつ、オーバーフローすることを防ぐことができます。

import java.util.*;

public class Main{
    static Scanner sc = new Scanner(System.in);

    static long x = sc.nextLong();
    static long y = sc.nextLong();
    static int t = (int)(x+y)/3;

    static long MOD = (int)1e9+7;

    static long[] facts = new long[t+1];

    public static void main(String[] args){
        facts[0] = 1;
        for (int i=1; i<t+1; i++){
            facts[i] = facts[i-1]*i %MOD;
        }

        if ((x+y)%3!=0){
            System.out.println(0);
            return;
        }

        long ans = 0;

        for (int i=0; i<t+1; i++){
            int a = i;
            int b = t-a;
            if (((a+b*2)!=x) || ((a*2+b)!=y)){
                continue;
            }
            ans += nck(t, a);
            ans %= MOD;
        }
        System.out.println(ans%MOD);
    }
    public static long modpow(long a, long b){
        if (b==0) return 1;
        else if (b==1) return a;
        long x = modpow(a, b/2);
        return b%2==0 ? x*x%MOD : x*(x*a%MOD)%MOD;
    }
    public static long inv(long n){
        return modpow(n, MOD-2);
    }
    public static long nck(int n, int k){
        return n<k ? 0: facts[n]*(inv(facts[n-k])*inv(facts[k])%MOD)%MOD;
    }
}

組み合わせ数を求めるためのCombinationクラスをライブラリ化したものが以下になります。

github.com

public class Combination{
    static int n = 7;   //　要素数
    static long MOD = (long)1e9+7;
    static long[] facts;

    public Combination(int n, long MOD){
        this.n = n;
        this.MOD = MOD;
        facts = new long[n+1];
        facts[0] = 1;
        for (int i=1; i<n+1; i++){
            facts[i] = facts[i-1]*i%MOD;
        }
    }

    public static void main(String[] args){
        facts = new long[n+1];
        facts[0] = 1;
        for (int i=1; i<n+1; i++){
            facts[i] = facts[i-1]*i%MOD;
        }
        System.out.println(nck(7,2));   // output 21
    }

    public static long modpow(long a, long b){  // 計算量はlog(MOD);
        if (b==0) return 1;
        else if (b==1) return a;
        long x = modpow(a, b/2);
        return b%2==0 ? x*x%MOD : x*(x*a%MOD)%MOD;
    }
    public static long inv(long n){ // 逆元。x^(-1)≡x^(p-2) (MOD p)
        return modpow(n, MOD-2);
    }
    public static long nck(int n, int k){
        return n<k ? 0: facts[n]*(inv(facts[n-k])*inv(facts[k])%MOD)%MOD;
    }
}