895C - Square Subsets - CodeForces Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <map>
#include <string.h>
#include <ctime>
#include <queue>
#include<unordered_map>
#include<stack>
#define ll long long
#define endl '\n'
using namespace std;

vector<int>dirx{ 1,-1, 0,0,1,1,-1,-1 };
vector<int>diry{ 0,0,-1,1,1,-1,1,-1 };

bool valid(int n, int m, int x, int y) {
	return x >= 0 && y >= 0 && x < n&& y < m;
}

ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return (a * b) / gcd(a, b);
}


const ll mod = 1e9 + 7, inf = 1e9, N = 1e5 + 5;
vector<int>p{ 2 };
void sieve() {
	vector<int>vis(70);
	for (int i = 3; i < 70; i+=2)
		if (!vis[i]) {
			p.push_back(i);
			for (int j = i * i; j < 70; j+=i)
				vis[j] = 1;
		}
}
ll fact[N], modinv[N];

ll fastpow(ll n, ll m) {
	ll ret = 1, t = n;
	while (m) {
		if (m & 1)
			ret *= t, ret %= mod;
		t *= t; t %= mod;
		m /= 2;
	}
	return ret % mod;
}

void pre() {
	fact[0] = 1;
	for (ll i = 1; i < N; i++)
		fact[i] = fact[i - 1] * i, fact[i] %= mod;
	modinv[N - 1] = fastpow(fact[N - 1], mod - 2);
	for (ll i = N - 2; i >= 0; i--)
		modinv[i] = (i + 1) * modinv[i + 1] % mod;

}

ll ncr(ll n, ll r) {
	return fact[n] * modinv[r] % mod * modinv[n - r] % mod;
}

int dp[71][1 << 19];
int n;
vector<int>a(75);
vector<pair<ll, ll>>odd_even(75);
int count(int i, int primes) {
	if (i == 71)
		if (!primes)
			return 1;
		else
			return 0;
	int& ret = dp[i][primes];
	if (~ret)
		return ret;
	ret = 0;
	ll temp = 0;
	if (a[i]) {
		ll odd_ways = odd_even[i].first, even_ways = odd_even[i].second;
		temp += even_ways * count(i + 1, primes);
		int num = i;
		for (int j = 0; j < p.size() && num>1; j++)
			while (num % p[j] == 0)
				num /= p[j], primes ^= (1 << j);
		temp += odd_ways * count(i + 1, primes);
		temp %= mod;
	}
	else
		temp = count(i + 1, primes);
	temp %= mod;
	ret = temp;
	return ret;
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		a[x]++;
	}
	for (int i = 1; i <= 70; i++) {
		ll odd = 0, even = 0;
		if (a[i])
			for (int j = 0; j <= a[i]; j++)
				if (j & 1)
					odd += ncr(a[i], j), odd %= mod;
				else
					even += ncr(a[i], j), even %= mod;
		odd_even[i] = { odd,even };
	}
	memset(dp, -1, sizeof dp);
	cout << count(0, 0) - 1 << endl;

}


//void files() {
//
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	sieve();
	pre();

	/*int t; cin >> t;
	while (t--)*/
	solve();
}