卡牌

WeLikeStudying · 2022-04-22 19:55:33 · 题解

• 对自身的问题有了新的体会。
• 人生中有很多选择，要审慎地对待，果断地决定。

题意

• 题目链接。
• 有 n 个数，问从它们内部选取任何一个子集，求它们的乘积被所有选定的质数整除的方案数。

分析

• 在您想其它算法的时候您发现一个问题，它实际上是在求一个经典 \text{NPC} 问题的方案数：子集覆盖的方案数，您顿时心生警戒并思考为啥题目开的数据范围如此之大。
• 您忽然想到了一道类似这样的题目名叫寿司晚宴，它利用了一个十分平凡的数论性质来关照似乎很大的数据范围：小于 \sqrt w 的质因子超级少，但大于 \sqrt w 的质因子在每个数中至多出现一次。
• 您统计了一下，发现在这个数据范围下小于 \sqrt{2000} 的质因子只有 14 个，为您心目中的暴力提供了坚实的理论基础。
• 您马上就思考怎么计算才能用到这个性质呢？对于每个大的因子，如果在它上面进行某个计算，由于不存在包含两个因子的数，它有个很好的特性就是它不会互相影响，我们或许可以用它进行状态压缩动态规划。
• 您发现这个就不错：f(A,B) 表示使用 A 中的数，然后使得它们的乘积能恰好被前十四个质数中的集合 B 整除的方案数，虽然您目前并不知道怎么计算。
• 不过您并不打算抛弃它，因为它具有相当优秀的性质：对于一个质数集合 p_1,p_2,\cdots ,p_n，你把前 14 个质数算出来，然后把 p_1 倍数的情况，p_2 倍数的情况……和除去这些质数的倍数的情况答案一一合并，您就相当于默认选了这些质数，然后全局的情况就是答案。
• 然后您发现了美好的性质，即我们加入的数的总个数不超过 w\log\log w，似乎相当有用。
• 实际上，预处理似乎可以直接暴力 O(2^{\pi(\sqrt w)}w\log\log w) 跑就可以了，接下来考虑合并的情况：对于 A\cap B=\varnothing： f(A\cup B,S)=\sum_{P\cup Q=S}f(A,P)f(B,Q)
• 这个是经典问题，可以用快速沃尔什变换解决。
• 但是您发现仍然无法避免在每次询问的时候要一个个加入求出它的 f 函数的问题，这或许是悲剧性的。
• 但是咱们可以把式子逆过来变成求逆元，也就是说对于 A\subseteq B，我们解方程： f(B,S)=\sum_{P\cup Q=S}f(A-B,P)f(B,Q)
• 这看似令人吐血，不过您理解了 \text{FWT} 的实质，所以它就是个除法求逆元的问题。
• 所以我们就可以一开始求解 O(\pi(w)) 个质数的倍数和全局的情况，总复杂度为 O(w\ln\ln w 2^{\pi(\sqrt w)})。
• 对于单次询问，我们使用所有质数不特殊处理（包含空集）的情况，用 \text{FWT} 合并，求逆，乘上全局的情况，得到不包含这些质数的情况，然后让所有质数的情况不包含空集进行处理，乘上不包含所有质数的情况，总复杂度为 O(\sum c_i\pi(\sqrt w)2^{\pi(\sqrt w)})，但是预处理多一点就可以每次询问几乎全都在暴力做乘除法，只需要一次 \text{FWT}。
• 综上，总复杂度应该是（什么玩意）（设 \pi(n) 为小于 n 的质数个数）： O(n+2^{\pi(\sqrt w)}(w\log\log w+(\pi(w)+m)\pi(\sqrt w)+\sum c_i))
• 卡常：只需要 13 个质数，因为 41\times47>2000。
• 对于求逆元，它可以加在预处理复杂度上，但是我们可以有更加好的方法，设 g(A,B) 为 \text{FWT} 变换的结果，容易利用它的意义：然后使得它们的乘积能恰好被前十四个质数中的集合 B 的某个子集整除的方案数，然后发现它的所有元素都是 2 的幂，预处理二的幂，我们可以用加减法代替求逆元，代码实现。