1735. 构造乘积数组的方案数

Hard

题目描述

给你一个二维整数数组 queries。对于每个 queries[i]，其中 queries[i] = [ni, ki]，请你找出有多少种不同的方法可以将正整数放入大小为 ni 的数组中，使得这些整数的乘积为 ki。由于方案数可能很大，第 i 个查询的答案需要对 10^9 + 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 % (10^9 + 7) = 50734910。

示例 2：

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

约束条件：

1 <= queries.length <= 10^4
1 <= ni, ki <= 10^4

解题思路

这是一道组合数学和数论的综合题目。核心思想是将问题转化为质因数分配问题。

思路分析：

质因数分解：首先对目标乘积 k 进行质因数分解，得到各个质数的指数
分配问题：将每个质因数的所有幂次分配到 n 个位置上，这是一个经典的"隔板法"组合问题
组合计算：对于质因数 p 出现 cnt 次，需要将这 cnt 个 p 分配到 n 个位置，允许某些位置为0，方案数为 C(cnt+n-1, n-1)
乘积原理：各个质因数的分配方案相互独立，最终答案是所有质因数分配方案数的乘积

实现要点：

预处理质因数分解：为了处理多个查询，预先计算出所有可能数字的最小质因数
组合数计算：预计算阶乘和逆元，支持快速组合数查询
模运算：所有运算都要在模 10^9+7 意义下进行

算法流程：

预处理1到10000的最小质因数（用于快速质因数分解）
预计算阶乘和阶乘的模逆元
对每个查询：质因数分解→计算各质因数的分配方案→相乘得到最终答案

代码实现

class Solution {
public:
    static const int MOD = 1e9 + 7;
    static const int MAXN = 10014;
    
    long long fact[MAXN], inv_fact[MAXN];
    int spf[MAXN]; // smallest prime factor
    
    long long power(long long a, long long b) {
        long long res = 1;
        while (b > 0) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    void precompute() {
        // Sieve for smallest prime factor
        for (int i = 1; i < MAXN; i++) spf[i] = i;
        for (int i = 2; i * i < MAXN; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j < MAXN; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        
        // Factorials and inverse factorials
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        inv_fact[MAXN-1] = power(fact[MAXN-1], MOD - 2);
        for (int i = MAXN - 2; i >= 0; i--) {
            inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
        }
    }
    
    long long comb(int n, int r) {
        if (r > n || r < 0) return 0;
        return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
    }
    
    vector<int> waysToFillArray(vector<vector<int>>& queries) {
        precompute();
        
        vector<int> result;
        for (auto& query : queries) {
            int n = query[0], k = query[1];
            
            // Prime factorization of k
            map<int, int> primeCount;
            int temp = k;
            while (temp > 1) {
                int p = spf[temp];
                primeCount[p]++;
                temp /= p;
            }
            
            // Calculate answer
            long long ans = 1;
            for (auto& [prime, cnt] : primeCount) {
                ans = ans * comb(cnt + n - 1, n - 1) % MOD;
            }
            
            result.push_back(ans);
        }
        
        return result;
    }
};

class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        MAXN = 10014
        
        # Precompute factorials and inverse factorials
        fact = [1] * MAXN
        for i in range(1, MAXN):
            fact[i] = fact[i-1] * i % MOD
        
        def power(a, b):
            res = 1
            while b > 0:
                if b & 1:
                    res = res * a % MOD
                a = a * a % MOD
                b >>= 1
            return res
        
        inv_fact = [1] * MAXN
        inv_fact[MAXN-1] = power(fact[MAXN-1], MOD - 2)
        for i in range(MAXN-2, -1, -1):
            inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
        
        def comb(n, r):
            if r > n or r < 0:
                return 0
            return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD
        
        # Sieve for smallest prime factor
        spf = list(range(MAXN))
        for i in range(2, int(MAXN**0.5) + 1):
            if spf[i] == i:
                for j in range(i*i, MAXN, i):
                    if spf[j] == j:
                        spf[j] = i
        
        def prime_factorization(num):
            factors = {}
            while num > 1:
                p = spf[num]
                factors[p] = factors.get(p, 0) + 1
                num //= p
            return factors
        
        result = []
        for n, k in queries:
            prime_count = prime_factorization(k)
            ans = 1
            for cnt in prime_count.values():
                ans = ans * comb(cnt + n - 1, n - 1) % MOD
            result.append(ans)
        
        return result

public class Solution {
    private const int MOD = 1000000007;
    private const int MAXN = 10014;
    
    private long[] fact = new long[MAXN];
    private long[] invFact = new long[MAXN];
    private int[] spf = new int[MAXN];
    
    private long Power(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    private void Precompute() {
        // Sieve for smallest prime factor
        for (int i = 1; i < MAXN; i++) spf[i] = i;
        for (int i = 2; i * i < MAXN; i++) {
            if (spf[i] == i) {
                for (int j = i * i; j < MAXN; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        
        // Factorials and inverse factorials
        fact[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        invFact[MAXN-1] = Power(fact[MAXN-1], MOD - 2);
        for (int i = MAXN - 2; i >= 0; i--) {
            invFact[i] = invFact[i+1] * (i+1) % MOD;
        }
    }
    
    private long Comb(int n, int r) {
        if (r > n || r < 0) return 0;
        return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
    }
    
    public int[] WaysToFillArray(int[][] queries) {
        Precompute();
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int n = queries[i][0], k = queries[i][1];
            
            // Prime factorization of k
            var primeCount = new Dictionary<int, int>();
            int temp = k;
            while (temp > 1) {
                int p = spf[temp];
                primeCount[p] = primeCount.GetValueOrDefault(p, 0) + 1;
                temp /= p;
            }
            
            // Calculate answer
            long ans = 1;
            foreach (var cnt in primeCount.Values) {
                ans = ans * Comb(cnt + n - 1, n - 1) % MOD;
            }
            
            result[i] = (int)ans;
        }
        
        return result;
    }
}

var waysToFillArray = function(queries) {
    const MOD = 1000000007;
    const MAXN = 10014;
    
    // Precompute factorials and inverse factorials
    const fact = new Array(MAXN);
    fact[0] = 1;
    for (let i = 1; i < MAXN; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    function power(a, b) {
        let res = 1;
        while (b > 0) {
            if (b & 1) res = (res * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }
    
    const invFact = new Array(MAXN);
    invFact[MAXN-1] = power(fact[MAXN-1], MOD - 2);
    for (let i = MAXN - 2; i >= 0; i--) {
        invFact[i] = (invFact[i+1] * (i+1)) % MOD;
    }
    
    function comb(n, r) {
        if (r > n || r < 0) return 0;
        return (fact[n] * invFact[r] % MOD * invFact[n-r]) % MOD;
    }
    
    // Sieve for smallest prime factor
    const spf = new Array(MAXN);
    for (let i = 1; i < MAXN; i++) spf[i] = i;
    for (let i = 2; i * i < MAXN; i++) {
        if (spf[i]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(√N + Q·log K)	预处理筛法O(√N)，每个查询质因数分解O(log K)
空间复杂度	O(N)	存储筛法数组、阶乘数组等

其中 N = 10^4，Q 是查询数量，K 是单个查询中的数值大小。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目