CF895C Square Subsets

给一个数组，求满足乘积为平方数的非空子集有多少个。

对于平方数，满足每个质数因子的指数为偶数，将每个数写作一个二进制数，每一位表示该质数因子的指数模二，那么乘积相当于异或，问题转化为异或和为 $0$ 的非空子集有多少个。

将所有数插入线性基，线性基大小为 $cnt$ ，那么剩下的 $n - cnt$ 可以随意选择，减去一个空集即为答案。

另外一个做法是状压DP。

查看代码

#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, cnt, bs[N];
vector <int> p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};
int binpow (int b, int k)
{
    int res = 1;
    while (k)
    {
        k & 1 && (res = (LL)res * b % mod);
        b = (LL)b * b % mod;
        k >>= 1;
    }
    return res;
}
void insert (int x)
{
    for (int i = p.size() - 1; ~i; i--)
        if (x >> i & 1)
        {
            if (!bs[i])
                return bs[i] = x, cnt++, void();
            x ^= bs[i];
        }
}
int main ()
{
    read(n);
    for (int i = 1, k; i <= n; i++)
    {
        int t = 0;
        read(k);
        for (int i = 0; i < p.size(); i++)
            for (; k % p[i] == 0; k /= p[i])
                t ^= 1 << i;
        insert(t);
    }
    write((binpow(2, n - cnt) - 1 + mod) % mod);
    return 0;
}