class Solution {
public:
vector<int> waysToFillArray(vector<vector<int>>& queries) {
}
};
1735. 生成乘积数组的方案数
给你一个二维整数数组 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原站题解
rust 解法, 执行用时: 48 ms, 内存消耗: 4.1 MB, 提交时间: 2023-10-25 22:52:16
impl Solution {
pub fn ways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
fn factor(mut n: i32) -> Vec<usize> {
let mut ans = vec![];
for i in 2..2+(n as f64).sqrt() as i32 {
let mut c = 0;
while n % i == 0 {
c += 1;
n /= i;
}
if c > 0 {
ans.push(c);
}
if n == 1 {
break;
}
}
if n > 1 {
ans.push(1);
}
ans
}
let mut comb = vec![vec![0; 15]; 10015];
let mo = 1_000_000_007;
comb[0][0] = 1;
for i in 1..comb.len() {
comb[i][0] = 1;
for j in 1..comb[i].len() {
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mo;
}
}
let mut ans = vec![];
for q in queries {
let mut bb = 1i64;
for a in factor(q[1]) {
bb = comb[a + q[0] as usize - 1][a] * bb % mo;
}
ans.push(bb as i32);
}
ans
}
}
rust 解法, 执行用时: 212 ms, 内存消耗: 4.5 MB, 提交时间: 2023-10-25 22:52:01
use std::collections::{BinaryHeap, HashMap, HashSet};
impl Solution {
pub fn ways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
fn decomposePrimeFactors() -> Vec<HashMap<usize, usize>> {
let size = 10000;
let mut ps = vec![HashMap::new(); size + 1];
for i in 2..ps.len() {
if ps[i].is_empty() {
ps[i].insert(i, 1);
let mut t = 2;
while i * t <= size {
if ps[i * t].is_empty() {
ps[i * t].insert(i, t);
}
t += 1;
}
} else {
let (x, c) = ps[i].drain().next().unwrap();
ps[i].insert(x, 1);
let b = ps[c].clone();
for a in b {
*ps[i].entry(a.0).or_insert(0) += a.1;
}
}
}
ps
}
fn fastpow(x: i32, mut a: i32) -> i32 {
let mut ans = 1i64;
let mut p = x as i64;
while a > 0 {
if a & 1 > 0 {
ans *= p;
ans %= 1_000_000_007;
}
a >>= 1;
p *= p as i64;
p %= 1_000_000_007;
}
ans as _
}
fn factor() -> (Vec<i32>, Vec<i32>) {
let size = 10015;
let mut fac = vec![0; size];
let mut inv = vec![0; size];
fac[0] = 1;
inv[0] = 1;
let mut num = 1i64;
for i in 1..fac.len() {
num = (num * i as i64) % 1_000_000_007;
fac[i] = num as _;
inv[i] = fastpow(num as _, 1_000_000_007 - 2);
}
(fac, inv)
}
let (fac, inv) = factor();
let pfs = decomposePrimeFactors();
let mut ans = vec![];
let mo = 1_000_000_007;
for q in queries {
let mut b = 1i64;
for (_, &a) in &pfs[q[1] as usize] {
b = fac[a + q[0] as usize - 1] as i64 * inv[q[0] as usize - 1] as i64 % mo * inv[a] as i64 % mo * b % mo;
}
ans.push(b as i32);
}
ans
}
}
python3 解法, 执行用时: 336 ms, 内存消耗: 20.6 MB, 提交时间: 2023-10-25 22:51:23
import math
MOD = 10 ** 9 + 7
class Solution:
@staticmethod
def getPrimes(n):
primes = []
for i in range(2, n):
flag = 0
for j in range(2, int(i**0.5)+1):
if (i % j == 0):
flag = 1
break
if not flag: primes.append(i)
return primes
def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
result = []
primes = self.getPrimes(100)
for query in queries:
n, k = query
ways = 1
for prime in primes:
if prime > k:
break
cnt = 0
while k % prime == 0:
# 尝试用 prime 分解 k
cnt += 1
k /= prime
ways *= math.comb(n + cnt - 1, cnt)
if k > 1:
# 如果最后 k > 1，那么说明 k 无法进一步被分解
# 此时 k 是一个比较大的质数，比如 2377
# 只要把 k 放在 n 个格子的任意一个位置，所以有 n 种放法
ways = ways * n
result.append(ways % MOD)
return result
cpp 解法, 执行用时: 60 ms, 内存消耗: 27.7 MB, 提交时间: 2023-10-25 22:49:51
using LL = long long;
class Solution {
private:
static constexpr int mod = 1000000007;
static constexpr int nmax = 10000;
static constexpr int logkmax = 13;
static int c[nmax + logkmax][logkmax + 1];
static bool inited;
vector<int> factors;
int n, k;
int sum;
int u;
public:
// 预处理组合数
void init() {
if (inited) {
return;
}
inited = true;
c[0][0] = 1;
for (int i = 1; i < nmax + logkmax; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i && j <= logkmax; ++j) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= mod) {
c[i][j] -= mod;
}
}
}
}
vector<int> waysToFillArray(vector<vector<int>>& queries) {
init();
vector<int> ans;
for (const auto& q: queries) {
int n = q[0], k = q[1];
int sum = 1;
for (int i = 2; i * i <= k; ++i) {
if (k % i == 0) {
int y = 0;
while (k % i == 0) {
++y;
k /= i;
}
sum = (LL)sum * c[n + y - 1][y] % mod;
}
}
if (k != 1) {
sum = (LL)sum * n % mod;
}
ans.push_back(sum);
}
return ans;
}
};
int Solution::c[nmax + logkmax][logkmax + 1] = {0};
bool Solution::inited = false;
cpp 解法, 执行用时: 52 ms, 内存消耗: 31.3 MB, 提交时间: 2023-10-25 22:49:20
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;
}
};
cpp 解法, 执行用时: 80 ms, 内存消耗: 29.8 MB, 提交时间: 2023-10-25 22:49:12
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;
}
};