作者推荐
本文涉及知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode:2338. 统计理想数组的数目
给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。
对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：
每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。
返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。
示例 1：
输入：n = 2, maxValue = 5
输出：10
解释：存在以下理想数组：
- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
- 以 2 开头的数组（2 个）：[2,2]、[2,4]
- 以 3 开头的数组（1 个）：[3,3]
- 以 4 开头的数组（1 个）：[4,4]
- 以 5 开头的数组（1 个）：[5,5]
共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。
示例 2：
输入：n = 5, maxValue = 3
输出：11
解释：存在以下理想数组： - 以 1 开头的数组（9 个）：
- 不含其他不同值（1 个）：[1,1,1,1,1]
- 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
- 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以 2 开头的数组（1 个）：[2,2,2,2,2]
- 以 3 开头的数组（1 个）：[3,3,3,3,3]
共计 9 + 1 + 1 = 11 个不同理想数组。
提示：
2 <= n <= 104
1 <= maxValue <= 104
动态规划
令 m =maxValue
直接动态规划超时
dp[i][j]记录 长度为i，以j结尾的子序列数量。状态数：O(mn)，每种状态转移的时间复杂度:O(m \sqrt mm)。约1010，超时。
预处理
vNext[i]包括x，表示x被i整除，且大于i，且<=maxValue。此部分的时间复杂度 和空间复杂度都是O(mm \sqrt {m}m)。
动态规划除重后的数量
除重后，最大长度14 {20,21 ,⋯ \cdots⋯,2^13}，令p= 14。
dp1[i][j] 记录除重后，长度为i，以j结尾的数量。空间复杂😮(qm) 转移所有dp[i]的时间复杂度:O(mm \sqrt {m}m)，总时间复杂度：O(nmm \sqrt mm)
dp[0]忽略，dp[1][0]为0，其它为1。
通过前者状态更新后置状态。 F o r x : v N e x t [ j ] \Large For_{x:vNext[j]}Forx:vNext[j]dp[i][x] += dp[i][j]
动态规划
dp2[i][j] 从i个不同的数中选择j个数的选择数量，每个数至少选择一个。枚举后置状态。
d p [ i ] [ j ] = ∑ x : 1 j d p [ i − 1 ] [ j − x ] dp[i][j] =\sum _{x:1}^{j} dp[i-1][j-x]dp[i][j]=x:1∑jdp[i−1][j−x]
必须通过前缀和优化，否则时间复杂度😮(qnn)，超时。
返回值
∑ x : 1 q ( ∑ ( d p 1 [ x ] ) ⋆ ( ∑ ( d p 2 [ x ] ) ) \sum _{x:1}^{q} (\sum(dp1[x])\star (\sum(dp2[x]))x:1∑q(∑(dp1[x])⋆(∑(dp2[x]))
代码
核心代码
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; } 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;; }; class Solution { public: int idealArrays(int n, int maxValue) { vector<vector<int>> vNext(maxValue + 1); for (int i = 1; i <= maxValue; i++) { for (int j = i * 2; j <= maxValue; j += i) { vNext[i].emplace_back(j); } } const int q = 14; vector<vector<C1097Int<> >> dp1(q + 1, vector<C1097Int<> >(maxValue + 1)); dp1[1].assign(maxValue + 1,1); dp1[1][0] = 0; for (int i = 1; i < q; i++) { for(int j = 0 ; j <= maxValue; j++ ) { for (const auto& next : vNext[j]) { dp1[i + 1][next] += dp1[i][j]; } } } vector<vector<C1097Int<> >> dp2(q + 1, vector<C1097Int<> >(n + 1)); dp2[0][0] = 1; for (int i = 1; i <= q; i++) { C1097Int biSum = dp2[i - 1][0]; for (int j = 1; j <= n; j++) { dp2[i][j] = biSum; biSum += dp2[i - 1][j]; } } C1097Int biRet; for (int i = 1; i <= q; i++) { biRet += std::accumulate(dp1[i].begin(),dp1[i].end(),C1097Int())* dp2[i].back(); } return biRet.ToInt(); } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int n, maxValue; { Solution sln; n = 2, maxValue = 5; auto res = sln.idealArrays(n, maxValue); Assert(res,10); } { Solution sln; n = 5, maxValue = 3; auto res = sln.idealArrays(n, maxValue); Assert(res, 11); } { Solution sln; n = 1000, maxValue = 1000; auto res = sln.idealArrays(n, maxValue); Assert(res, 91997497); } { Solution sln; n = 10000, maxValue = 10000; auto res = sln.idealArrays(n, maxValue); Assert(res, 22940607); } }
2023年2月
class Solution {
public:
int idealArrays(int n, int maxValue) {
m_n = n;
m_vPosNeedSel.assign(n + 1, vector(20, 0));
m_vPosNeedSel[1].assign(20,1);
for (int i = 2; i <= n; i++)
{
for (int j = 0; j < 20; j++)
{
//全部选择第一个位置
m_vPosNeedSel[i][j] += 1;
//第一个位置选择k个
for (int k = 0; k < j; k++)
{
m_vPosNeedSel[i][j] += m_vPosNeedSel[i - 1][j-k];
}
}
}
for (int i = 1; i <= maxValue; i++ )
{
Do(i);
}
return m_iRet.ToInt();
}
void Do(int i)
{
C1097Int aNum = 1 ;
for (int j = 2; j*j <= i; j++)
{
int iNumj = 0;
while (0 == i% j)
{
iNumj++;
i /= j;
}
aNum *= m_vPosNeedSel[m_n][iNumj];
}
if (i > 1)
{
aNum *= m_vPosNeedSel[m_n][1];
}
m_iRet += aNum;
}
vector<vector> m_vPosNeedSel;
int m_n;
C1097Int m_iRet = 0;
};
