Untitled
unknown
plain_text
a year ago
1.8 kB
11
Indexable
#include <iostream> #include <array> #include <vector> #include <algorithm> #include <set> #include <cmath> #include <queue> #include <map> #include <cassert> #include <iomanip> #include <cstring> #include <stack> #include <bitset> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); const int N = 170; const long long mod = 1e9 + 7; int basis[170] = {}, sz = 0; vector<bitset<N>>v(1001); void add(int n){ bitset<170> cur = v[n]; for (int i = 0; i < 170; ++i){ if (cur[i] == 0) continue; if (basis[i] == 0){ basis[i] = cur[i]; ++sz; return ; } cur ^= basis[i]; } } void solve(){ int n; cin >> n; int total = 0; int freq[1001] = {}; for (int i = 0 ; i < n; ++i){ int x; cin >> x; freq[x] = 1; } vector<bool>isprime(1001, true); int num = 0; for (int i = 2; i <= 1000; ++i){ if (isprime[i]){ for (int j = i; j <= 1000; j += i){ int cur = j; while(cur % i == 0){ cur /= i; v[j][num] = 1 - v[j][num]; } if (i != j) isprime[j] = false; } ++num; } } for (int i = 2; i <= 1000; ++i) if (freq[i]) add(i); long long cur = n - sz; long long ans = 1; for (int i = 1; i <= cur; ++i) ans = (2 * ans) % mod; ans = (ans - 1) % mod; ans = (ans + mod) % mod; cout << ans; } int main(){ fast; int t = 1; //cin >> t; for (int i = 1; i <= t; ++i){ solve(); if (i != t) cout << '\n'; } }
Editor is loading...
Leave a Comment