题目描述
给你一个二维整数数组 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=p1x1×p2x2×⋯×pmxm,其中 pi 为质数,而 xi 为 pi 的指数。那么题目实际上等价于:把 x1 个 p1, x2 个 p2, ⋯, xm 个 pm 分别放到 n 个位置上,单个位置可以为空,问有多少种方案。
根据组合数学的知识,我们把 x 个球放入 n 个盒子中,有两种情况:
如果盒子不能为空,那么方案数为 Cx−1n−1,这里是利用隔板法,即一共 x 个球,我们在其中 x−1 个位置插入 n−1 个隔板,从而将 x 个球分成 n 组。
如果盒子可以为空,那么我们可以再增加 n 个虚拟球,然后再利用隔板法,即一共 x+n 个球,我们在其中 x+n−1 个位置插入 n−1 个隔板,从而将实际的 x 个球分成 n 组,并且允许盒子为空,因此方案数为 Cx+n−1n−1。
因此,对于每个查询 queries[i],我们可以先对 k 进行质因数分解,得到指数 x1,x2,⋯,xm,然后计算 Cx1+n−1n−1,Cx2+n−1n−1,⋯,Cxm+n−1n−1,最后将所有的方案数相乘即可。
所以,问题转化为如何快速计算 Cmn,根据公式 Cmn=n!(m−n)!m!,我们可以先预处理出 m!,然后利用逆元快速计算 Cmn。
时间复杂度 O(K×loglogK+N+m×logK),空间复杂度 O(N)。
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 | N = 10020
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
p = defaultdict(list)
for i in range(1, N):
f[i] = f[i - 1] * i % MOD
g[i] = pow(f[i], MOD - 2, MOD)
x = i
j = 2
while j <= x // j:
if x % j == 0:
cnt = 0
while x % j == 0:
cnt += 1
x //= j
p[i].append(cnt)
j += 1
if x > 1:
p[i].append(1)
def comb(n, k):
return f[n] * g[k] * g[n - k] % MOD
class Solution:
def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
ans = []
for n, k in queries:
t = 1
for x in p[k]:
t = t * comb(x + n - 1, n - 1) % MOD
ans.append(t)
return ans
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | class Solution {
private static final int N = 10020;
private static final int MOD = (int) 1e9 + 7;
private static final long[] F = new long[N];
private static final long[] G = new long[N];
private static final List<Integer>[] P = new List[N];
static {
F[0] = 1;
G[0] = 1;
Arrays.setAll(P, k -> new ArrayList<>());
for (int i = 1; i < N; ++i) {
F[i] = F[i - 1] * i % MOD;
G[i] = qmi(F[i], MOD - 2, MOD);
int x = i;
for (int j = 2; j <= x / j; ++j) {
if (x % j == 0) {
int cnt = 0;
while (x % j == 0) {
++cnt;
x /= j;
}
P[i].add(cnt);
}
}
if (x > 1) {
P[i].add(1);
}
}
}
public static long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
public static long comb(int n, int k) {
return (F[n] * G[k] % MOD) * G[n - k] % MOD;
}
public int[] waysToFillArray(int[][] queries) {
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int n = queries[i][0], k = queries[i][1];
long t = 1;
for (int x : P[k]) {
t = t * comb(x + n - 1, n - 1) % MOD;
}
ans[i] = (int) t;
}
return ans;
}
}
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | int N = 10020;
int MOD = 1e9 + 7;
long f[10020];
long g[10020];
vector<int> p[10020];
long qmi(long a, long k, long p) {
long res = 1;
while (k != 0) {
if ((k & 1) == 1) {
res = res * a % p;
}
k >>= 1;
a = a * a % p;
}
return res;
}
int init = []() {
f[0] = 1;
g[0] = 1;
for (int i = 1; i < N; ++i) {
f[i] = f[i - 1] * i % MOD;
g[i] = qmi(f[i], MOD - 2, MOD);
int x = i;
for (int j = 2; j <= x / j; ++j) {
if (x % j == 0) {
int cnt = 0;
while (x % j == 0) {
++cnt;
x /= j;
}
p[i].push_back(cnt);
}
}
if (x > 1) {
p[i].push_back(1);
}
}
return 0;
}();
int comb(int n, int k) {
return (f[n] * g[k] % MOD) * g[n - k] % MOD;
}
class Solution {
public:
vector<int> waysToFillArray(vector<vector<int>>& queries) {
vector<int> ans;
for (auto& q : queries) {
int n = q[0], k = q[1];
long long t = 1;
for (int x : p[k]) {
t = t * comb(x + n - 1, n - 1) % MOD;
}
ans.push_back(t);
}
return ans;
}
};
|
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56 | const n = 1e4 + 20
const mod = 1e9 + 7
var f = make([]int, n)
var g = make([]int, n)
var p = make([][]int, n)
func qmi(a, k, p int) int {
res := 1
for k != 0 {
if k&1 == 1 {
res = res * a % p
}
k >>= 1
a = a * a % p
}
return res
}
func init() {
f[0], g[0] = 1, 1
for i := 1; i < n; i++ {
f[i] = f[i-1] * i % mod
g[i] = qmi(f[i], mod-2, mod)
x := i
for j := 2; j <= x/j; j++ {
if x%j == 0 {
cnt := 0
for x%j == 0 {
cnt++
x /= j
}
p[i] = append(p[i], cnt)
}
}
if x > 1 {
p[i] = append(p[i], 1)
}
}
}
func comb(n, k int) int {
return (f[n] * g[k] % mod) * g[n-k] % mod
}
func waysToFillArray(queries [][]int) (ans []int) {
for _, q := range queries {
n, k := q[0], q[1]
t := 1
for _, x := range p[k] {
t = t * comb(x+n-1, n-1) % mod
}
ans = append(ans, t)
}
return
}
|