1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/count-ways-to-make-array-with-product/description

2.解题方法

2.1.解题思路

排列组合+插板法求将k个相同的球放入n个不同的桶中（每个桶中至少一个球）

2.2.解题步骤

第一步，使用递推式预处理组合数

第二步，遍历每个item。item_i=(n_i,k_i)，n_i为构造长度，k_i为乘积。先将k_i进行质因数分解，并统计每个质因数a的个数b，对于每b个质因数a，将其放到n_i个桶中，使用插板法获取组合数为c_i。所有c的乘积即为k_i的结果，将其加入result数组中

3.解题代码

Python代码

# 获取一个正整数的各个分解的质因素及数量;生成的item为(质因数,数量)
def getNumFactors(num):
    factor=2
    while factor*factor<=num:
        if num%factor==0:
            cnt=0
            while num%factor==0:
                cnt+=1
                num=num//factor
            yield (factor,cnt)
        factor+=1
    if num>1:
        yield (num,1)

class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        MOD=10**9 + 7
        # 第一步，使用递推式预处理组合数
        maxM,maxN=10**4+15,15
        comb=[[0]*maxN for _ in range(maxM)]
        for i in range(maxM):
            comb[i][0]=1
        for i in range(1,maxM):
            for j in range(1,min(maxN,i+1)):
                comb[i][j]=(comb[i-1][j]+comb[i-1][j-1]) % MOD
        # 第二步，遍历每个item。item_i=(n_i,k_i)，n_i为构造长度，k_i为乘积。先将k_i进行质因数分解，并统计每个质因数a的个数b，对于每b个质因数a，将其放到n_i个桶中，使用插板法获取组合数为c_i。所有c的乘积即为k_i的结果，将其加入result数组中
        result=[]
        for n,k in queries:
            total=1
            for factor,cnt in getNumFactors(k):
                # 每个质数使用插空法进行
                total=(total*comb[cnt+n-1][cnt])%MOD
            result.append(total)
        return result

4.执行结果