1735. 生成乘积数组的方案数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个二维整数数组 queries ，其中 queries[i] = [ni, ki] 。第 i 个查询 queries[i] 要求构造长度为 ni 、每个元素都是正整数的数组，且满足所有元素的乘积为 ki ，请你找出有多少种可行的方案。由于答案可能会很大，方案数需要对 109 + 7 取余。

请你返回一个整数数组 answer，满足 answer.length == queries.length ，其中 answer[i]是第 i 个查询的结果。

示例 1：

输入：queries = [[2,6],[5,1],[73,660]]
输出：[4,1,50734910]
解释：每个查询之间彼此独立。
[2,6]：总共有 4 种方案得到长度为 2 且乘积为 6 的数组：[1,6]，[2,3]，[3,2]，[6,1]。
[5,1]：总共有 1 种方案得到长度为 5 且乘积为 1 的数组：[1,1,1,1,1]。
[73,660]：总共有 1050734917 种方案得到长度为 73 且乘积为 660 的数组。1050734917 对 109 + 7 取余得到 50734910 。

示例 2 ：

输入：queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：[1,2,3,10,5]

提示：

1 <= queries.length <= 10⁴
1 <= ni, ki <= 10⁴

# 思路

排列组合 + 记忆化 + 模逆元。我的想法是首先求和不含1的因数的排列有多少种，比如16，它含有2个因数的排列有3种([2, 8],[8, 2], [3, 3])。再看题目要求生成的数组有多长，假设为10，那么对于长度2的排列而言，我们可以往其中插入8个1，其实就也是3 * C(10, 2)。按照这种思维，我们只需要通过递归不断求出每个数，不含1的每种长度的排列有多种即可。由于k小于10000且因数不含1，那么递归的过程其实是很快的(2^15 = 16384)。另外需要很多的记忆化操作，防止大量的重复计算而超时。最后一个重点是模逆元，这个是用于求大数的排列组合的。

# 解法

class Solution {
    private static int mod = 1_000_000_007;

    // 记忆化
    private static long[] mods = new long[20];
    static {
        for(int i = 0; i < mods.length; i++) {
            mods[i] = modReverse(i);
        }
    }
    public int[] waysToFillArray(int[][] queries) {
        int[] ans = new int[queries.length];
        Set<Integer>[] sets = new Set[10001];
        for(int i = 0; i < sets.length; i++) {
            sets[i] = new HashSet<>();
        }
        int[] cn = new int[15];
        int n, k;
        for(int i = 0; i < queries.length; i++) {
            n = queries[i][0];
            k = queries[i][1];
            if(k == 1) {
                ans[i] = 1;
                continue;
            }
            dfs(n, k, sets, cn, 0);
            for(int j = 0; j < cn.length; j++) {
                // 这里用comine(n, j) 而不是combine(n, n - j), 这是因为j不超过15，当n较大时，计算速度快得多
                // 这也提示我们不放过任何优化的细节，思考清楚每一个细节。
                ans[i] += combine(n, j) * cn[j] % mod;
                ans[i] = ans[i] % mod;
                cn[j] = 0;
            }
        }
        return ans;
    }


    // 求某个n的因数集(不含1)
    private Set<Integer> decompose(int n) {
        Set<Integer> s = new HashSet<>();
        for(int i = 2; i * i <= n + 1; i++) {
            if(n % i == 0) {
                s.add(i);
                s.add(n / i);
            }
        }
        s.add(n);
        return s;
    }

    // 求不含1的因子的组合数
    private void dfs(int n, int k, Set<Integer>[] sets, int[] cn, int cur) {
        if(k == 1) {
            cn[cur]++;
            return;
        }
        if(sets[k].size() == 0) {
            sets[k] = decompose(k);
        }
        for(int m : sets[k]) {
            if(n >= 1) {
                dfs(n - 1, k / m, sets, cn, cur + 1);
            }
        }
    }

    // 求组合数(这个和下面的模逆元函数基本上都是固定写法)
    private long combine(int m, int n) {
        long ans = 1L;
        for(int i = 1; i <= n; i++) {
            ans = ans * (m - i + 1) % mod * mods[i] % mod;
        }
        return ans;
    }

    // 求模逆元，主要是解决大数的排列组合问题
    private static long modReverse(int n) {
        long ans = 1L, m = mod - 2, p = n;
        while(m > 0) {
            if((m & 1) == 1) {
                ans = ans * p % mod;
            }
            p = p * p % mod;
            m = m >> 1;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

# 总结

分析出几种情况，然后分别对各个情况实现

#Java