{"id":8017,"date":"2021-01-23T21:29:33","date_gmt":"2021-01-24T05:29:33","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8017"},"modified":"2021-01-23T21:29:51","modified_gmt":"2021-01-24T05:29:51","slug":"leetcode-1735-count-ways-to-make-array-with-product","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1735-count-ways-to-make-array-with-product\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1735. Count Ways to Make Array With Product"},"content":{"rendered":"\n

You are given a 2D integer array, queries<\/code>. For each queries[i]<\/code>, where queries[i] = [ni<\/sub>, ki<\/sub>]<\/code>, find the number of different ways you can place positive integers into an array of size ni<\/sub><\/code> such that the product of the integers is ki<\/sub><\/code>. As the number of ways may be too large, the answer to the ith<\/sup><\/code> query is the number of ways modulo<\/strong> 109<\/sup> + 7<\/code>.<\/p>\n\n\n\n

Return an integer array <\/em>answer<\/code> where <\/em>answer.length == queries.length<\/code>, and <\/em>answer[i]<\/code> is the answer to the <\/em>ith<\/sup><\/code> query.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> queries = [[2,6],[5,1],[73,660]]\nOutput:<\/strong> [4,1,50734910]\nExplanation:<\/strong> Each query is independent.\n[2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1].\n[5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1].\n[73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 109<\/sup> + 7 = 50734910.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]\nOutput:<\/strong> [1,2,3,10,5]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= queries.length <= 104<\/sup><\/code><\/li>
  • 1 <= ni<\/sub>, ki<\/sub> <= 104<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution1: DP<\/strong><\/h2>\n\n\n\n
    let dp(n, k) be the ways to have product k of array size n.
    dp(n, k) = sum(dp(n – 1, i)) where i is a factor of k and i != k.
    base case:
    dp(0, 1) = 1, dp(0, *) = 0
    dp(i, 1) = C(n, i)
    e.g. 
    dp(2, 6) = dp(1, 1) + dp(1, 2) + dp(1, 3) 
    = 2 + 1 + 1 = 4
    dp(4, 4) = dp(3, 1) + dp(3, 2) 
    = dp(3, 1) + dp(2, 1)
    = 4 + 6 = 10
    <\/p>\n\n\n\n
    Time complexity: O(sum(k_i))?
    Space complexity: O(sum(k_i))?<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector waysToFillArray(vector>& queries) {\n    constexpr int kMod = 1e9 + 7;\n    int n = 0;\n    unordered_map c, dp;\n    function cnk = [&](int n, int k) {\n      if (k > n) return 0;\n      if (k == 0 || k == n) return 1;      \n      int& ans = c[(n << 16) | k];\n      if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod; \n      return ans;      \n    };\n    \n    function dfs = [&](int s, int k) -> int {\n      if (s == 0) return k == 1;\n      if (k == 1) return cnk(n, s);\n      int& ans = dp[(s << 16) | k];\n      if (ans) return ans;      \n      for (int i = 1; i * i <= k; ++i) {\n        if (k % i) continue;\n        if (i != 1) \n          ans = (ans + dfs(s - 1, k \/ i)) % kMod;\n        if (i * i != k)\n          ans = (ans + dfs(s - 1, i)) % kMod;\n      }\n      return ans;\n    };\n    \n    vector ans;\n    for (const auto& q : queries) {\n      dp.clear();\n      n = q[0];\n      ans.push_back(dfs(n, q[1]));\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 2D integer array, queries. For each queries[i], where queries[i] = [ni, ki], find the number of different ways you can place positive integers into…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,441,217,59],"class_list":["post-8017","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-factor","tag-hard","tag-prime","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8017","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8017"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8017\/revisions"}],"predecessor-version":[{"id":8019,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8017\/revisions\/8019"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8017"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8017"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8017"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}