結果
問題 | No.803 Very Limited Xor Subset |
ユーザー |
![]() |
提出日時 | 2019-03-14 17:43:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 966 bytes |
コンパイル時間 | 1,527 ms |
コンパイル使用メモリ | 173,036 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-07 17:40:56 |
合計ジャッジ時間 | 2,685 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)typedef long long ll;const ll mod=1e9+7 ;using B=bitset<350>;using mat = vector<B>;int solve(mat a,int& rank) {int h = a.size(), w = a[0].size();rep(j,w){int pivot = -1;REP(i, rank, h) if(a[i][j]) {pivot = i; break;}if(pivot == -1) continue;swap(a[rank], a[pivot]);rep(i, h) if(i != rank && a[i][j]) a[i] ^= a[rank];rank++;}return rank;}int main(){int n,m;cin>>n>>m;int z;cin>>z;B x(z);mat a(n);rep(i,n){int p;cin>>p;a[i]=p;}rep(i,m){int type,l,r;cin>>type>>l>>r;--l;REP(j,l,r)a[j][i+30]=1;if(type)x[i+30]=1;}int rank1=0,rank2=0;solve(a,rank1);a.push_back(x);solve(a,rank2);if(rank1!=rank2){cout<<0<<endl;return 0;}ll ans=1;rep(i,n-rank1)ans=ans*2%mod;cout<<ans<<endl;return 0;}