Square

推荐题目：NOI2015T3，2022省选联考T4。

题意是：在 $P = [1, 2, 3, \dots , n]$ 选择子集 $X$，$X\sub P$，记 $f(X)$ 表示集合的元素的乘积。不存在 $p \in \mathbb N^+$，$p^2 \mid f(X)$。计算这样的集合 $X$ 的个数，对大质数取模。

I 转化题意

不难发现原命题相当于令 $f(X) = d$，将其质因数分解成 $p_i^{a_i}$， $p_i$ 是质数，有 $\forall\ 0 < a_i \le 1$。

于是，你想到状压，记下质因数的指数是 $0$ 还是 $1$。

设 $R_{i, j, S}$ 表示已经考虑到 $i$，共选了 $j$，此时的 $f(X)$ 的质因数分解的情况为 $S$。

转移简单（真的简单），预处理每个数的质因数分解的 $mask_x$，去掉能被 $p^2$ 整除的，做一遍 DP。

$R_{i, j, S} = R_{i-1, j, S} + R_{i-1, j-1, S \oplus mask_i}$。

最后输出答案就行了。

II 优化DP

不难发现 $500$ 以内的质数比较多，状态开不下，上面的 DP，只有 50pts。

所以考虑优化，你发现一些质数比如说 $79$，它的指数最多为 $1$，因为 $79^2 > 500$。所以类似地，$p \ge \sqrt{500}, p\text{ is prime}$，他们的指数最多只有 $1$，它们最多选 $1$ 个。

故修改下原来的定义：$mask_i$ 仍旧去掉含平方因子的数字，只有前 $10$ 个质数的指数的状态。

综此，我们设计出如下 DP。

将每个整数找出最大的质因子，如果比 $\sqrt{500}$，大叫做大数，小的叫做小数。

对相同最大质因子的大数分别做分组背包，所有小数做 01 背包。滚动数组搞上来。

复杂度 $\mathcal{O}(2^n\times n^2)$