题目描述
给定一个二维整数数组 queries
,其中 queries[i] = [n_i, k_i]
。第 i
个查询 queries[i]
要求构造长度为 n_i
、每个元素都是正整数的数组,且满足所有元素的乘积为 k_i
,请你找出有多少种可行的方案。由于答案可能会很大,方案数需要对 10^9 + 7
取余。
请返回一个整数数组 answer
,满足 answer.length == queries.length
,其中 answer[i]
是第 i
个查询的结果。
样例
输入: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。
输入:queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出:[1,2,3,10,5]
限制
1 <= queries.length <= 10^4
1 <= n_i, k_i <= 10^4
算法
(动态规划,组合数学) $O(n \log k )$
- 设状态 $f(i, j)$ 表示构造长度为 $i$ 的数组,且乘积为 $j$ 时的方案数。这里假定每次填充的数字大于 1。
- 初始时,$f(0, 0) = 1$,其余待定。
- 转移时,对于 $f(i - 1, j)$,枚举这一次填充的数字 $k$,转移 $f(i, j * k) = f(i, j * k) + f(i - 1, j)$。
- 对于查询 $(n, k)$,由于需要补充包含 1 的方案数,所以需要枚举非 1 的个数,将所有情况累加。故最终答案为 $\sum_{t = 0}^{\min(c, n)}{f(t, k) \cdot \tbinom{n}{t}}$,这里的 $c$ 为 $n$ 分解质因数的个数。
- 计算组合数可以通过阶乘和乘法逆元的方式进行。
时间复杂度
- 动态规划不能直接定义数组计算,可以采用哈希表的方式存储。由于每个数字 $k$ 最多有 $O(\log k)$ 个质因数,所以其最多在 $O(\log k)$ 个哈希表中存在。由于转移时间为常数,所以动态规划的时间复杂度为 $O(n \log k)$。
- 累加答案同理,需要 $O(n \log k)$ 的时间。
- 故总时间复杂度为 $O(n \log k)$。
空间复杂度
- 需要 $O(n \log k)$ 的空间存储动态规划的状态和阶乘的预处理的值。
C++ 代码
#define LL long long
#define mod 1000000007
class Solution {
private:
LL power(LL x, LL y) {
LL tot = 1, p = x;
for (; y; y >>= 1) {
if (y & 1)
tot = tot * p % mod;
p = p * p % mod;
}
return tot;
}
public:
vector<int> waysToFillArray(vector<vector<int>>& queries) {
vector<unordered_map<int, LL>> f(10001);
f[0][1] = 1;
vector<LL> fac(10001);
fac[0] = 1;
for (int i = 1; i <= 10000; i++)
fac[i] = fac[i - 1] * i % mod;
int n = 1, m = 1;
for (const auto &q : queries) {
if (n < q[0]) n = q[0];
if (m < q[1]) m = q[1];
}
for (int i = 1; i <= n; i++)
for (const auto &it: f[i - 1])
for (int k = 2; it.first * k <= m; k++)
f[i][it.first * k] = (f[i][it.first * k] + it.second) % mod;
vector<int> ans;
for (const auto &q : queries) {
LL res = 0, c = 0;
int t = q[1];
for (int i = 2; i * i <= t; i++) {
while (t % i == 0) {
t /= i;
c++;
}
}
if (t > 1) c++;
for (int i = 0; i <= q[0] && i <= c; i++)
res = (res + f[i][q[1]] * fac[q[0]] % mod *
power(fac[i], mod - 2) % mod *
power(fac[q[0] - i], mod - 2) % mod) % mod;
ans.push_back(res);
}
return ans;
}
};
设状态 f(i,j) 表示构造长度为 i 的数组,且乘积为 j 时的方案数。这里假定每次填充的数字大于 1。
为什么地方不能直接填1
理论上是可以的吧
直接带上 1 硬算复杂度不可接受
好的 明白了
第3步的状态转移该如何理解呀
手动模拟一下,就是个递推累加
第3步的状态转移该如何理解呀