题解 CF895C 【Square Subsets】

我们设 \(x=\prod p_i^{k_i}\)，考虑什么时候 \(x\) 是完全平方数。容易发现如果所有 \(k_i\) 都是偶数，此时 \(\sqrt{x}=\prod p_i^{\frac{k_i}{2}}\) 为整数，即 \(x\) 是完全平方数；否则 \(x\) 不是完全平方数。

题目转换为原序列 \(\{a_i\}\) 有多少个非空子集乘积质因数分解后质数均为偶数。

发现奇偶性是满足异或性质的，奇数对应 \(1\)，偶数对应 \(0\)。考虑将原序列的每一个 \(a_i\) 进行质因数分解，将分解后每个质因数的指数奇偶性二进制压位成一个整数，存到线性基中。

假设线性基中有 \(cnt\) 个元素，那么剩下的 \(n-cnt\) 个数可以用线性基的元素异或表示，可以任意取，共有 \(2^{n-cnt}\) 种取法，注意减掉全都不取的一种就是答案。

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const int N = 1e5+5, mod = 1e9+7;
const int pm[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};

int n, a[N];
template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}
struct LinearBasis {
	int p[19];
	LinearBasis() {memset(p, 0, sizeof(p));}
	~LinearBasis() {}
	void insert(int x) {
		per(i, 18, 0) {
			if(!((x >> i) & 1)) continue;
			if(!p[i]) {p[i] = x; return;}
			x ^= p[i];
		}
	}
	int qmax() {
		int ans = 0; 
		per(i, 18, 0) chkmax(ans, ans^p[i]);
		return ans;
	}
	int cnt() {
		int ans = 0;
		per(i, 18, 0) ans += !!p[i];
		return ans;
	}
}LB;
int qpow(int x, int y) {
	int ans = 1;
	for(;y;y>>=1,x=1LL*x*x%mod) if(y & 1) ans = 1LL * ans * x % mod;
	return ans;
}

int main() {
	scanf("%d", &n);
	rep(i, 1, n) {
		scanf("%d", &a[i]);
		int now = 0;
		per(j, 18, 0) {
			now <<= 1;
			while(!(a[i] % pm[j])) {
				now ^= 1;
				a[i] /= pm[j];
			}
		}
		LB.insert(now);
	}
	printf("%d\n", (qpow(2, n-LB.cnt())+mod-1)%mod);
    return 0;
}