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

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

这题想要计算的是，将一个数K分解成为N个数，有多少种组合。考虑到n, k <= 10 ** 4, 所以这题用简单的搜索是不行的。

凡是涉及到整数的分解，一定要想到从质数角度进行考虑。假设6 = (2 ** 1) * (3 * 1). 如果要分解成为3个数的话，那么其实变成了两个问题：

  1. 将2的指数(这里是1)分解成为3个数，有 [0,0,1], [0,1,0], [1,0,0] 三种
  2. 将3的指数（这里是1）分解成为3个数，和上面一样，有 [0,0,1], [0,1,0], [1,0,0] 三种

每种质数的分法最后乘在一起就是结果，也就是9种。

原问题变为，将一个数X拆分成为N个数，使得这些数的和是X，有多少种方法。如果k <= 10 ** 4 的话，那么X肯定不会超过13。这个问题就是一个典型的动态规划，空间是O(N * X), 时间复杂度是O(N * X * X). 

class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:

        # import functools
        # @functools.lru_cache(maxsize = None)
        # def DP(n, k):
        #     if (k == 0): return 1
        #     if (n == 1): return 1
        #     res = 0
        #     for k1 in range(0, k+1):
        #         res += DP(n-1, k-k1)
        #     return res

        N = max((x[0] for x in queries))
        DP = [[0] * (N+1) for _ in range(20)]
        DP = [[0] * 20 for _ in range(N+1)]
        DP[0] = [1] * 20
        DP[1] = [1] * 20

        for i in range(2, N+1):
            for k in range(0, 20):
                ans = 0
                for k1 in range(0, k+1):
                    ans += DP[i-1][k-k1]
                DP[i][k] = ans

        # print(DP[3][10])


        PMS = [0] * 101
        for i in range(2, 100):
            if PMS[i] == 1: continue
            for j in range(i, 100):
                if i * j >= 100: break
                PMS[i * j] = 1
        PS = []
        for i in range(2, 100):
            if PMS[i] == 0: PS.append(i)

        # print(PS)

        MOD = 10 ** 9 + 7
        def test(n, k):
            ans = 1
            for p in PS:
                if k % p == 0:
                    cnt = 0
                    while k % p == 0:
                        cnt += 1
                        k = k // p
                    res = DP[n][cnt]
                    # print(n, p, cnt, res)
                    ans = ans * res

            if k != 1:
                ans = ans * DP[n][1]
            ans = ans % MOD
            return ans


        ans = []
        for n, k in queries:
            res =  test(n, k)
            ans.append(res)
        return ans