結果
| 問題 |
No.1167 Graduation Trip
|
| ユーザー |
chocorusk
|
| 提出日時 | 2020-08-12 01:53:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,111 ms / 4,000 ms |
| コード長 | 2,924 bytes |
| コンパイル時間 | 2,141 ms |
| コンパイル使用メモリ | 144,904 KB |
| 最終ジャッジ日時 | 2025-01-12 20:53:24 |
|
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
using uint=unsigned int;
uint a[10010];
vector<int> Gauss_Jordan(vector<int> &v){ //v[i]<2^MAX
int n=v.size();
vector<uint> w(n);
for(int i=0; i<n; i++) w[i]=a[v[i]];
vector<bool> b(n);
for(int i=0; i<32; i++){
int p=-1;
for(int j=0; j<n; j++){
if(b[j]) continue;
if((w[j]>>i)&1){
b[j]=1;
p=j;
break;
}
}
if(p==-1) continue;
for(int j=p+1; j<n; j++){
if((w[j]>>i)&1){
w[j]^=w[p];
}
}
}
vector<int> ret;
for(int j=0; j<n; j++){
if(b[j]) ret.push_back(v[j]);
}
return ret;
}
template<typename T>
struct SparseTable{
using F=function<T(T, T)>;
const F f;
const T e;
vector<vector<T>> spt;
vector<int> vlog;
SparseTable(const F f, const T &e, const vector<T> &v):f(f), e(e){
int b=0, n=v.size();
while((1<<b)<=n) b++;
spt.resize(b, vector<T>(n));
for(int i=0; i<n; i++) spt[0][i]=v[i];
for(int i=1; i<b; i++){
for(int j=0; j+(1<<i)<=n; j++){
spt[i][j]=f(spt[i-1][j], spt[i-1][j+(1<<(i-1))]);
}
}
vlog.resize(n+1);
for(int i=2; i<=n; i++) vlog[i]=vlog[i>>1]+1;
}
T query(int l, int r){
int b=vlog[r-l];
return f(spt[b][l], spt[b][r-(1<<b)]);
}
};
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
ll ap=a, ans=1;
while(k){
if(k&1){
ans*=ap;
ans%=MOD;
}
ap=ap*ap;
ap%=MOD;
k>>=1;
}
return ans;
}
ll inv(ll a){
return powmod(a, MOD-2);
}
int main()
{
int n, q;
cin>>n>>q;
for(int i=0; i<n; i++) cin>>a[i];
auto f=[&](vector<int> v, vector<int> w){
v.insert(v.end(), w.begin(), w.end());
return Gauss_Jordan(v);
};
vector<vector<int>> va(n);
for(int i=0; i<n; i++) if(a[i]>0) va[i].push_back(i);
vector<int> e;
SparseTable<vector<int>> seg(f, e, va);
while(q--){
int m; cin>>m;
int pr=0;
int sum=0;
for(int i=0; i<m; i++){
int b; cin>>b;
int r=seg.query(pr, b).size();
sum+=b-pr-r;
pr=b;
}
sum+=n-pr-(int)seg.query(pr, n).size();
cout<<powmod(2, sum)<<endl;
}
return 0;
}
chocorusk