結果
| 問題 |
No.1167 Graduation Trip
|
| ユーザー |
沙耶花
|
| 提出日時 | 2021-04-07 15:57:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,406 ms / 4,000 ms |
| コード長 | 1,565 bytes |
| コンパイル時間 | 4,406 ms |
| コンパイル使用メモリ | 259,740 KB |
| 最終ジャッジ日時 | 2025-01-20 12:49:46 |
|
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
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;
}
vector<long long> op(vector<long long> A,vector<long long> B){
while(B.size()>0){
A.push_back(B.back());
B.pop_back();
}
Func(A);
return A;
}
vector<long long> e(){
return vector<long long>(0);
}
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};
}
segtree<vector<long long>,op,e> 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.prod(l,r).size();
ans = mod(ans * beki(2,r-l-t));
}
cout<<ans<<endl;
}
return 0;
}
沙耶花