Untitled

 avatar
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