1735-生成乘积数组的方案数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

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

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

示例 1：

**输入：** 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 对 109 + 7 取余得到 50734910 。

示例 2 ：

**输入：** queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
**输出：** [1,2,3,10,5]

提示：

  • 1 <= queries.length <= 104
  • 1 <= ni, ki <= 104

对k进行质因数分解:k=\displaystyle\prod_{i=1}^mp_i^{r_i.
设数组中第j个数为a_j,且a_j=\displaystyle\prod_{i=1}^mp_i^{r_{ij},那么对每个i=1,\cdots,m,有\displaystyle\sum_{j=1}^nr_{ij}=r_i.
由于每个方程是相互独立的,如果记方程\displaystyle\sum_{j=1}^nr_{j}=r的非负整数解数量为w(n,r),根据乘法原理答案为k=\displaystyle\prod_{i=1}^mw(n,r_i).

记n,k的最大值分别为N,K,询问数量为Q.

第一个问题:如何对k进行质因数分解
第一种做法是单独考虑每个k,用每个小于\sqrt k的数试除k,那么需要O(\sqrt k)的时间.
第二种做法是用筛法预处理,那么需要O(K\log\log K)的预处理时间.

第二个问题:如何求解w(n,r),注意到r=O(\log k).
第一种做法是使用动态规划,根据c_n是否为0可以得到w(n,r)=w(n,r-1)+w(n-1,r),需要O(N\log K)的时间.
第二种做法是用插板法考虑组合意义,可以得到w(n,r)=\binom{n+r-1}{r.
可以不作任何预处理直接计算组合数,复杂度为O(\min(n,r)\log\text{mod}).
也可以O(N+\log K)预处理阶乘及其逆元,然后O(1)计算组合数.

参考代码
1.不使用任何预处理进行计算,复杂度为O(Q(\sqrt K+\log K\log\text{mod}).

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
constexpr int mod = 1'000'000'007;
int power(int a, int r){
    int res = 1;
    for(; r; r >>= 1, a = 1LL * a * a % mod)
        if(r & 1) res = 1LL * res * a % mod;
    return res;
}
int inv(int n){
    return power(n, mod - 2);
}
int C(int m, int n){
    int res = 1;
    for(int i = 0; i < n; i += 1) res = 1LL * res * (m - i) % mod;
    for(int i = 1; i <= n; i += 1) res = 1LL * res * inv(i) % mod;
    return res;
}
class Solution {
public:
    vector<int> waysToFillArray(vector<vector<int>>& queries) {
        vector<int> res;
        for(auto v : queries){
            int n = v[0], k = v[1], ans = 1;
            for(int i = 2, r; i * i <= k; i += 1)
                if(k % i == 0){
                    for(r = 0; k % i == 0; k /= i) r += 1;
                    ans = 1LL * ans * C(n + r - 1, r) % mod;
                }
            if(k > 1) ans = 1LL * ans * n % mod;
            res.push_back(ans);
        }
        return res;
    }
};

2.尽可能使用预处理,复杂度为O(K\log\log K+N+Q\log K).

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
constexpr int mod = 1'000'000'007;
constexpr int maxn = 10000 + 13;
int f[maxn], g[maxn];
vector<int> rs[maxn];
int C(int m, int n){
    return 1LL * f[m] * g[n] % mod * g[m - n] % mod;
}
class Solution {
public:
    vector<int> waysToFillArray(vector<vector<int>>& queries) {
        if(f[0] != 1){
            for(int i = 0; i < maxn; i += 1) f[i] = i ? 1LL * f[i - 1] * i % mod : 1;
            for(int i = 1; i < maxn; i += 1) g[i] = i == 1 ? 1 : 1LL * (mod - mod / i) * g[mod % i] % mod;
            for(int i = 0; i < maxn; i += 1) g[i] = g[i] ? 1LL * g[i - 1] * g[i] % mod : 1;
            for(int i = 2; i < maxn; i += 1){
                if(rs[i].empty()){
                    for(int j = i; j < maxn; j += i){
                        rs[j].push_back(0);
                        for(int k = j; k % i == 0; k /= i) rs[j].back() += 1;
                    }
                }
            }
        }
        vector<int> res;
        for(auto v : queries){
            int n = v[0], k = v[1], ans = 1;
            for(int r : rs[k]) ans = 1LL * ans * C(n + r - 1, r) % mod;
            res.push_back(ans);
        }
        return res;
    }
};
 Comments
On this page
1735-生成乘积数组的方案数