杂题选做2

P8292

题意：有 \(n\le 10^6\) 张卡片，卡片上有权值 \(a_i\)，有 \(m\le 1500\) 次询问，每次给定 \(c_i\) 个质数（\(\sum c_i \le 18000\)），要求选择的卡片乘积整除每一个给定质数的选择方案数。

值域是 \([1,2000]\)。

选法计数题，考虑容斥或者 dp。dp 显然对于大数据不好做，考虑容斥。

然后直接算方案数仍然不好做，继续考虑正难则反。枚举 \(i\) 个质数，计算至少不整除这几个质数的方案数，将可以整除他们的 \(a_i\) 全部去掉，剩下的显然随便选，设对于 \(i\) 的答案是 \(f_i\)，答案就是 \(\sum_{i = 0}^{c} f_i \times (-1)^{i}\)。

然后发现质数很多不好算，但是对于质因数题可以经典根号分治，对于这个题，每个数大于 \(43\) 的质因数最多只有一个，即互不影响可以暴算，所有数中不大于 \(43\) 的质因数只有 \(13\) 个，可以状压。

于是你预处理 \(f[S,i]\) 表示前几个质数的状态是 \(S\) 的情况下有 \(i\) 作为质因数的数有几个，那么容易发现对于一个状态 \(S\)，它的答案就是对于一个特殊的大质因数 \(k\)，如果询问对它有要求，就钦定不能一个都不选，乘上 \(2^f-1\)，否则乘上 \(2^f\) 即可。

然后直接压即可。