本文涉及知识点
【组合数学 隔板法 容斥原理】放球问题
乘法原理 唯一分解定理
本题同解
【唯一分解定理】【动态规划】【前缀和】1735生成乘积数组的方案数
LeetCode 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
唯一分解定理
根据唯一分解定理：x
∈
\in
∈ R ,可以分解a1m1a2m2
⋯
\cdots
⋯ akmk
其中ai >=2 。由于ki <= 104，故mi < 14，因为214 = 1024
×
\times
× 16 > 104。
本题
⟺
\iff
⟺ 独立的k步，将mi个ai分配给ni个元素。
每步的结果是放球问题，mi个相同的球，ni个不同的盒子，盒子可以为空。
根据乘法原理，总结果等于各步结果相乘。
代码
template<int MOD = 1000000007>
class C1097Int
{
public:
C1097Int(long long llData = 0) :m_iData(llData% MOD)
{
}
C1097Int operator+(const C1097Int& o)const
{
return C1097Int(((long long)m_iData + o.m_iData) % MOD);
}
C1097Int& operator+=(const C1097Int& o)
{
m_iData = ((long long)m_iData + o.m_iData) % MOD;
return *this;
}
C1097Int& operator-=(const C1097Int& o)
{
m_iData = (m_iData + MOD - o.m_iData) % MOD;
return *this;
}
C1097Int operator-(const C1097Int& o)
{
return C1097Int((m_iData + MOD - o.m_iData) % MOD);
}
C1097Int operator*(const C1097Int& o)const
{
return((long long)m_iData * o.m_iData) % MOD;
}
C1097Int& operator*=(const C1097Int& o)
{
m_iData = ((long long)m_iData * o.m_iData) % MOD;
return *this;
}
C1097Int operator/(const C1097Int& o)const
{
return *this * o.PowNegative1();
}
C1097Int& operator/=(const C1097Int& o)
{
*this /= o.PowNegative1();
return *this;
}
bool operator==(const C1097Int& o)const
{
return m_iData == o.m_iData;
}
bool operator<(const C1097Int& o)const
{
return m_iData < o.m_iData;
}
C1097Int pow(long long n)const
{
C1097Int iRet = 1, iCur = *this;
while (n)
{
if (n & 1)
{
iRet *= iCur;
}
iCur *= iCur;
n >>= 1;
}
return iRet;
}
C1097Int PowNegative1()const
{
return pow(MOD - 2);
}
int ToInt()const
{
return m_iData;
}
private:
int m_iData = 0;;
};
template<int MOD = 1000000007>
C1097Int<MOD> Pow(const C1097Int<MOD>& bi1, long long ii2) {
return bi1.pow(ii2);
}
template<class T >
class CFactorial
{
public:
CFactorial(int n):m_res(n+1){
m_res[0] = 1;
for (int i = 1; i <= n; i++) {
m_res[i] = m_res[i - 1] * i;
}
}
T Com(int iSel, int iCanSel)const {
return m_res[iCanSel] / m_res[iSel]/ m_res[iCanSel - iSel];
}
T Com(const vector<int>& cnt)const {
T biRet = 1;
int iCanSel = std::accumulate(cnt.begin(), cnt.end(), 0);
for (int j = 0; j < cnt.size(); j++) {
biRet *= Com(cnt[j], iCanSel);
iCanSel -= cnt[j];
}
return biRet;
}
vector<T> m_res;
};
template<class T>
class CBallBox
{
public:
CBallBox(CFactorial<T>& fac,int n,int m):m_fac(fac),m_iN(n),m_iM(m){
}
T NotNotNot() {//球不同盒子不同不能为空
return g(m_iM);
}
T NotIsNot() {//球不同盒子同不能为空
return NotNotNot()/ m_fac.m_res[m_iM];
}
T IsNotIs() {//球同盒子不同能为空
return m_fac.Com(m_iM - 1, m_iN + m_iM - 1);
}
const int m_iM, m_iN;
protected:
T g(int m)const {
T biRet;
for (int i = 0; i <= m; i++) {
auto cur = m_fac.Com(i, m) * Pow(T(m - i), m_iN);
if (1 & i) {
biRet -= cur;
}
else {
biRet += cur;
}
}
return biRet;
}
CFactorial<T>& m_fac;
};
class CUniqueFactorization
{
public:
CUniqueFactorization(int iMax) {
int iMaxSqrt = sqrt(iMax) + 2;
m_vPrime = CreatePrime(iMaxSqrt);
}
void Factorization(int x) {
m_a.clear();
m_n.clear();
for (const auto& iPre : m_vPrime) {
int cnt = 0;
while (0 == x % iPre) {
cnt++;
x /= iPre;
}
if (cnt > 0) {
m_a.emplace_back(iPre);
m_n.emplace_back(cnt);
}
}
if (x > 1) {
m_a.emplace_back(x);
m_n.emplace_back(1);
}
}
vector<int> m_a, m_n;
vector<int> CreatePrimeOld(int iMax)
{
vector<int> vNo(iMax + 1);
vector<int> vPrime;
for (int i = 2; i <= iMax; i++)
{
if (!vNo[i])
{
vPrime.emplace_back(i);
}
for (const auto& n : vPrime)
{
if (n * i > iMax)
{
break;
}
vNo[n * i] = true;
}
}
return vPrime;
}
vector<int> CreatePrime(int iMax)
{
vector<bool> isPrime(iMax + 1, true);
vector<int> vPrime;
for (int i = 2; i <= iMax; i++)
{
if (isPrime[i])
{
vPrime.emplace_back(i);
}
for (const auto& n : vPrime)
{
if (n * i > iMax) { break; }
isPrime[n * i] = false;
if (0 == i % n) { break; }
}
}
return vPrime;
}
vector<int> m_vPrime;
};
class Solution {
public:
vector<int> waysToFillArray(vector<vector<int>>& queries) {
static vector<vector<C1097Int<>>> vCnt = Init();
vector<int> ret;
CUniqueFactorization uf(m_iC);
for (auto& v : queries) {
uf.Factorization(v[1]);
C1097Int<> cur = 1;
for (const auto& cnt : uf.m_n) {
cur *= vCnt[cnt][v[0]];
}
ret.emplace_back(cur.ToInt());
}
return ret;
}
vector<vector<C1097Int<>>> Init()
{
CFactorial<C1097Int<>> fac(m_iR + m_iC);
vector<vector<C1097Int<>>> vCnt(m_iR, vector<C1097Int<>>(m_iC + 1));
for (int i = 1; i < m_iR; i++) {
for (int j = 1; j <= m_iC; j++) {
CBallBox<C1097Int<>> ballBox(fac, i, j);
vCnt[i][j] = ballBox.IsNotIs();
}
}
return vCnt;
}
const int m_iR = 14, m_iC = 10000;
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
![[LitCTF 2023]yafu (中级) （素数分解）](https://img-blog.csdnimg.cn/direct/71f4ed8317ab4e829f089146738cffe0.png)
![[leetcode hot150]第二百三十六题，二叉树的最近公共祖先](https://img-blog.csdnimg.cn/direct/2426ff478b5b4dad8b639a88bbf68263.png)
