Untitled
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