Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.0 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;
int basis[M], 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
    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;
        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;
                }
            }
        }
    }
}

void add(int n)
{
    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[i];
            ++sz;
            return;
        }
        cur ^= basis[i];
    }
}

bool found(bitset<N> &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
    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--)
    {
        memset(basis, 0, sizeof basis);
        sz = 0;
        int l, r; cin >> l >> r;
        for (int i = 1; i <= 1000; ++i)
        {
            if (prefix[r][i] - prefix[l - 1][i] > 0)
                add(i);
        }
        int x; cin >> x;
        bitset<N> 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;
}
Leave a Comment