解题思路

• 乘积为平方数意味着该乘积的每个质因子的指数之和都是偶数。
• 我们可以将每个数 $a_i$ 进行质因数分解，只关心每个质因子指数的奇偶性（模 $2$ 余数）。指数为奇数记为 $1$，偶数记为 $0$，最终得到一个由 $0/1$ 组成的向量（或压缩成一个二进制掩码）。
• 选择若干个数相乘，对应位置的指数奇偶性会进行异或（模 $2$ 加法）运算。若最终掩码为全 $0$，则乘积为平方数。
• 因为 $n \le 20$，我们可以枚举所有非空子集（共 $2^n - 1$ 种），对每个子集计算掩码异或和，异或和为 $0$ 则方案数加一。
• 具体步骤：
  1. 预处理出 $100$ 以内的所有质数。
  2. 对每个 $a_i$，依次用这些质数试除，统计每个质因子的指数奇偶性，压缩进一个整数掩码 mask[i]。