过题随笔 | 擅长解密的小红同学

import java.util.Scanner;

public class Main {
    static final int M = 1000000007;
    static final int N = 1000000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] a = new int[10];
        long sum = 0;
        long fac = 1;

        long[] fact = new long[N + 1];
        fact[0] = 1;
        for (int i = 1; i < N + 1; ++i) {
            fact[i] = (i * fact[i - 1]) % M;
        }

        for (int i = 0; i <= 9; ++i) {
            a[i] = in.nextInt();
            sum = (sum + a[i]) % M;
            fac = (fac * fact[a[i]]) % M;
        }
        long sumf = 1;
        if (sum > N) {
            sumf = fact[N];
            for (int i = N+1; i <= sum; ++i) {
                sumf = (sumf * i) % M;
            }
        } else {
            sumf = fact[(int)sum];
        }
        long fac_inv = pow(fac, M - 2) % M;
        long ans = (sumf * fac_inv) % M;
        System.out.println(ans);
    }
    static long pow(long n, int m) {
        long res = 1;
        while (m > 0) {
            if ((m & 1) == 1) {
                res = (res * n) % M;
            }
            n = (n * n) % M;
            m >>= 1;
        }
        return res % M;
    }
}

调了好久最后才发现是阶乘写错了。

这题我一开始是想不出来的，看了题解之后才做出来的。主要用到了费马小定理求逆元(里面有快速幂)，然后就是计算期望的值，化为排列的值。还是用了多重集的排列公式。不错。今天很晚了，就先到这吧