可以直接爆搜,也可以写逐位确定的多项式复杂度算法,使用多重组合式求随意乱排的方案数.
首先对 (A) 所有数暴力分解质因数,然后把遇到过的质因数打上标记.
根据期望的线性性,我们考虑每种颜色对答案的贡献.
可以发现贡献只与颜色出现次数有关,注意到本质不同的出现次数只有 (sqrt{n}) 个,于是我们把出现次数相同的颜色一起计算贡献,复杂度 (mathcal{O}(n sqrt{n})).
首先考虑什么情况是合法的.
同时继续观察可以发现:我们可以放宽条件使得答案依然不变(令 (s_j) 为 (j) 这个公司可以接受的菜品压位构成的二进制数):
接下来考虑第二问,根据第一问可以得知,问题显然可以转化为:
考虑容斥,计算得到不合法的方案数.
可以发现,问题在于如何快速地得到选出若干个集合并集恰好为 (S) 的容斥系数之和.
对此,我们考虑使用 另一个容斥来求出此容斥系数之和.
那么就满足二项式反演的集合形式,令 (f) 为恰好的方案,根据二项式反演易得:
那么最终第二问的答案为: