結果
問題 |
No.1167 Graduation Trip
|
ユーザー |
![]() |
提出日時 | 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; }