网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P7224
2024-07-06
P7224 [RC-04] 子集积 (背包 dp + 复杂度优化)
P7224[RC-04]子集积背包dp+复杂度优化考虑dp。容易想到背包dp,设\(f_{i,j}\)表示考虑了前\(i\)个,当前乘积为\(j\)的方案数。枚举\(a_i\)的倍数转移。复杂度\(O(\sum\limits_{i=1}^n\frac{m}{a_i})\)。如果\(a_i\)互不相同,那么近似于\(O(m\lnm)\)。如果还想