过题随笔 | 【模板】组合数（JAVA）|费马小定理求逆元（快速幂）+预处理

import java.io.*;

public class Main {
    //快读快写
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static int Mod = 1000000007;
    static long[] fac_inv = new long[500005];
    static long[] fac = new long[500005];
    public static void main(String[] args) throws IOException{
        int t = nextInt();
        fac[0] = 1;
        for (int i = 1;i <= 500000;++i) fac[i] = fac[i-1]*i%Mod;
        fac_inv[500000] = inv((int)fac[500000]);
        for (int i = 499999; i >= 0;--i) fac_inv[i] = fac_inv[i+1]*(i+1)%Mod;
        for (int tp = 1;tp <= t;++tp) {
            int n = nextInt();
            int m = nextInt();
            out.print(combine(m,n)+"\n");
            out.flush();
        }
    }
    static long combine(int m, int n) {
        long ans = 1;
        ans = ((fac[m]*fac_inv[m-n])%Mod *fac_inv[n])%Mod;
        return ans;
    }
    static long inv(int n) {return quickPow(n,Mod-2);}
    static long quickPow(long n,int q) {
        long ans = 1;
        while (q != 0) {
            if ((q&1) == 1) ans = ans*n%Mod;
            q >>= 1;
            n = n*n%Mod;
        }
        return ans;
    }
}

每日一题模板题做起来还是比较舒服的，不太可能磕太久。这一题数据量比较大。我还以为是IO的速度问题，后面才发现要有比较完备的预处理，才能过这题。

阶乘预处理比较简单了，逆元预处理我就是看题解才看懂。。这个公式应该是可以拆开运算然后证明的，但是我不太确认逆元的分配律那些东西，还是数学基础不够扎实。

逆元是拿来计算除法模运算的。

费马小定理，快速幂，快读快写的JAVA板子如上。注意费马小定理只能用于质数取模求逆元。1e9+7这个数字很常见了，是个质数噢。