# Untitled

unknown
plain_text
a month ago
3.1 kB
4
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

const int M = 170, N = 1001 ; /// Number of primes up to 1000 is 169
const int mod = 1e9 + 7;
bitset<M> basis[M];
int sz;
vector<bitset<M>> primes(N); ///v[num][i] = 1, if num has odd number of the ith prime
vector<bool>isprime(N, true);
vector<int> index(N, -1), powers_of_2(N); /// Store the index for each prime

void pre()
{
isprime[0] = isprime[1] = false;
int num = 0; // to get the index of each prime
for (int i = 2; i < N; ++i)
{
if (isprime[i])
{
index[i] = num++;
primes[i][index[i]] = 1;
for (int j = i + i; j < N; j += i)
{
isprime[j] = false;
int cur_num = j;
while(cur_num % i == 0)
{
primes[j][index[i]] = 1 - primes[j][index[i]]; /// Flip
cur_num /= i;
}
}
}
}
}

{
if (n == 0)
return;
bitset<M> cur = primes[n];
for (int i = 0 ; i < M; ++i)
{
if (cur[i]  == 0)
continue;
if (basis[i] == 0)
{
basis[i] = cur;
++sz;
return;
}
cur ^= basis[i];
}
}

bool found(bitset<M> &cur)
{
for (int i = 0; i < M; ++i)
{
if (cur[i] == 0)
continue;
if (basis[i] == 0)
return false;
cur ^= basis[i];
}
return true;
}

void solve(){
int n; cin >> n;
vector<vector<int>>prefix(n + 1, vector<int>(N)); /// To get number of occurrence
powers_of_2[0] = 1;
powers_of_2[1] = 2;
for (int i = 2; i <= n; ++i)
{
powers_of_2[i] = (1LL * powers_of_2[i - 1] * 2) % mod;
}
for (int i = 1; i <= n; ++i)
{
int x; cin >> x;
prefix[i][x] = 1;
for (int num = 1; num < N; ++num)
prefix[i][num] += prefix[i - 1][num];
}

int q; cin >> q;
while(q--)
{
sz = 0;
int l, r; cin >> l >> r;
for (int i = 0; i < M; ++i)
basis[i] = 0;
for (int i = 1; i <= 1000; ++i)
{
if (prefix[r][i] - prefix[l - 1][i] > 0)
}
int x; cin >> x;
bitset<M> cur;
while(x--)
{
int y; cin >> y;
cur[index[y]] = 1;
}
if (found(cur))
{
cout << powers_of_2[r - l + 1 - sz] << '\n';
}
else cout << 0 << '\n';
}
}

int main()
{
fast;
pre();
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("Error.txt", "w", stderr);
#endif
int t = 1; //cin >> t;
for (int i = 1 ; i <= t; ++i)
{
solve();
if (i != t)
cout << '\n';
}
return 0;
}```