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 an array of size ni such that the product of the integers is ki. As the number of ways may be too large, the answer to the ith query is the number of ways modulo 109 + 7.
Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.
Example 1:
Input: queries = [[2,6],[5,1],[73,660]] Output: [4,1,50734910] Explanation: Each query is independent. [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]. [5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1]. [73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 109 + 7 = 50734910.
Example 2:
Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]] Output: [1,2,3,10,5]
Constraints:
1 <= queries.length <= 1041 <= ni, ki <= 104
Solution1: DP
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
Time complexity: O(sum(k_i))?
Space complexity: O(sum(k_i))?
C++
|
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 |
// Author: Huahua class Solution { public: vector<int> waysToFillArray(vector<vector<int>>& queries) { constexpr int kMod = 1e9 + 7; int n = 0; unordered_map<int, int> c, dp; function<int(int, int)> cnk = [&](int n, int k) { if (k > n) return 0; if (k == 0 || k == n) return 1; int& ans = c[(n << 16) | k]; if (!ans) ans = (cnk(n - 1, k - 1) + cnk(n - 1, k)) % kMod; return ans; }; function<int(int, int)> dfs = [&](int s, int k) -> int { if (s == 0) return k == 1; if (k == 1) return cnk(n, s); int& ans = dp[(s << 16) | k]; if (ans) return ans; for (int i = 1; i * i <= k; ++i) { if (k % i) continue; if (i != 1) ans = (ans + dfs(s - 1, k / i)) % kMod; if (i * i != k) ans = (ans + dfs(s - 1, i)) % kMod; } return ans; }; vector<int> ans; for (const auto& q : queries) { dp.clear(); n = q[0]; ans.push_back(dfs(n, q[1])); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment