結果
| 問題 |
No.1167 Graduation Trip
|
| ユーザー |
沙耶花
|
| 提出日時 | 2020-08-12 00:30:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 843 ms / 4,000 ms |
| コード長 | 2,007 bytes |
| コンパイル時間 | 2,525 ms |
| コンパイル使用メモリ | 206,100 KB |
| 最終ジャッジ日時 | 2025-01-12 20:45:53 |
|
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 100000000000000000
void Func(vector<long long> &A){
int last = 0;
for(long long i=31;i>=0;i--){
int ind = -1;
for(int j=last;j<A.size();j++){
if((A[j]>>i) & 1LL){
ind = j;
break;
swap(A[j],A[last]);
ind = last;
last++;
break;
}
}
if(ind==-1)continue;
for(int j=0;j<A.size();j++){
if(j!=ind){
if((A[j]>>i)&1LL){
A[j] ^= A[ind];
}
}
}
swap(A[last],A[ind]);
last++;
}
while(A.size()!=0&&A.back()==0)A.pop_back();
return;
}
template <typename T>
struct sparse_table{
const T init_value = vector<long long>();
vector<T> v;
int n;
int sz;
sparse_table(vector<T> &x){
sz = x.size();
for(int i=0;true;i++){
if((1<<i)>sz){
n = i;
break;
}
}
v.resize(sz*n,init_value);
for(int i=0;i<sz;i++){
v[i] = x[i];
}
for(int i=1;i<n;i++){
for(int j=0;j<sz+1-(1<<i);j++){
int temp = j+(1<<(i-1));
v[i*sz+j] = func(v[(i-1)*sz+j],v[(i-1)*sz+temp]);
}
}
}
T query(int l,int r){
int x = 31-__builtin_clz(r-l);
return func(v[sz*x+l],v[sz*x+r-(1<<x)]);
}
T func(T a,T b){
while(b.size()!=0){
a.push_back(b.back());
b.pop_back();
}
Func(a);
return a;
}
};
int beki(long long a,long long b,int M = modulo){
int x = 1;
while(b!=0){
if(b&1){
x=((long long)x*a)%M;
}
a=((long long)a*a)%M;
b>>=1;
}
return x;
}
int main(){
int N,Q;
cin>>N>>Q;
vector<vector<long long>> A(N);
for(int i=0;i<N;i++){
long long t;
cin>>t;
A[i] = {t};
}
sparse_table<vector<long long>> S(A);
for(int i=0;i<Q;i++){
int M;
cin>>M;
vector<int> B(M);
for(int j=0;j<M;j++)cin>>B[j];
int ans = 1;
for(int j=0;j<=M;j++){
int l,r;
if(j!=0)l = B[j-1];
else l=0;
if(j!=M)r = B[j];
else r=N;
int t = S.query(l,r).size();
ans = mod(ans * beki(2,r-l-t));
}
cout<<ans<<endl;
}
return 0;
}
沙耶花