题解 CF895C 【Square Subsets】
eee_hoho
2020-09-17 08:17:32
考虑到完全平方数只和质因子次幂的奇偶性相关，那么我们可以把乘积转化为二进制下的异或。
于是题目变成选择若干个数异或起来为$0$的方案数。
那么考虑把所有元素插入到线性基中，于是不在线性基里的元素一定可以被线性基里的元素表示，相异或就可以为$0$。
而在线性基里的元素一定不会其他元素表示，相异或一定不为$0$。
所以方案数就是不在线性基中的元素个数组成的非空子集数：$2^{n-cnt}-1$
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e5;
const int P = 1e9 + 7;
using namespace std;
int n,a[N + 5],prime[N + 5],pcnt,vis[N + 5],val[N + 5],p[N + 5],cnt;
int mypow(int a,int x){int s = 1;for (;x;x & 1 ? s = 1ll * s * a % P : 0,a = 1ll * a * a % P,x >>= 1);return s;}
void prework()
{
for (int i = 2;i <= 70;i++)
{
if (!vis[i])
prime[++pcnt] = i;
for (int j = 1;prime[j] * i <= 70 && j <= pcnt;j++)
{
vis[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
void ins(int x)
{
for (int i = 22;i >= 0;i--)
if (x >> i & 1)
{
if (!p[i])
{
p[i] = x;
cnt++;
break;
}
x ^= p[i];
}
}
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]);
prework();
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= pcnt;j++)
while (a[i] % prime[j] == 0)
val[i] ^= 1 << j - 1,a[i] /= prime[j];
ins(val[i]);
}
int ans = mypow(2,n - cnt) - 1;
cout<<(ans + P) % P<<endl;
return 0;
}
```