結果

問題 No.803 Very Limited Xor Subset
ユーザー 沙耶花
提出日時 2020-11-28 17:55:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,232 bytes
コンパイル時間 1,768 ms
コンパイル使用メモリ 199,472 KB
最終ジャッジ日時 2025-01-16 09:31:06
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000000000
void Gauss(vector<bitset<333>> &B){
    int now = 0;
    rep(i,333){
        int temp = -1;
        for(int j=now;j<B.size();j++){
            if(B[j][i]){
                temp = j;
                break;
            }
        }
        if(temp==-1)continue;
        
        rep(j,B.size()){
            if(temp==j)continue;
            if(B[j][i])B[j] ^= B[temp];
        }
        
        swap(B[now],B[temp]);
        now++;
    }
}
int main(){
    
    int N,M,X;
    cin>>N>>M>>X;
    
    vector<bitset<333>> B(N);
    
    rep(i,N){
        int A;
        cin>>A;
        
        rep(j,30){
            if((A>>j)&1)B[i][j] = 1;
        }
    }
    
    bitset<333> XX;
    rep(i,30){
        if((X>>i)&1)XX[i] = 1;
    }
    
    rep(i,M){
        int t,l,r;
        cin>>t>>l>>r;
        l--;r--;
        for(int j=l;j<=r;j++){
            B[j][30+i] = 1;
        }
        if(t==1){
            XX[30+i] = 1;
        }
    }
    
    Gauss(B);
    
    
    rep(i,B.size()){
        rep(j,333){
            if(B[i][j]==1){
                if(XX[j])XX ^= B[i];
                break;
            }
        }
    }
    
    
    rep(i,333){
        if(XX[i]){
            cout<<0<<endl;
            return 0;
        }
    }
    
    mint ans = 1;
    rep(i,B.size()){
        bool f = false;
        rep(j,333){
            if(B[i][j]==1)f=true;
        }
        if(!f)ans *= 2;
    }
    cout<<ans.val()<<endl;
    
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0