ferinの競プロ帳

競プロについてのメモ

KUPC2012 K - XOR回廊

AtCoder

問題ページ
サイクル基底入門として解いた

サイクル基底・サイクルの個数について - 競プロ練習記録

グラフのサイクルについて扱いたいけれど，サイクルの個数は多すぎてどうしようもないみたいなときに使える話．サイクルの対称差を演算として考えると，いくつかの基本的なサイクルの集合を基底として考えることができる．DFS木(森)の後退辺と木辺からなるサイクルをサイクル基底の要素とすることでこれは実現できる．

対称差を取っている都合上，コストがXORだとうれしい．s-tパスとサイクル基底に含まれるサイクルの対称差を取った辺集合は，s-tパスのうち奇数回通ることが可能な辺の集合になる．s-tパスを通るのにかかるコストとサイクル基底の部分集合を通るのにかかるコストのXORを最大化するような，サイクル基底の部分集合を選ぶような問題に帰着できた．

根から x, y までのコスト c_x, x_y をあらかじめ求めておくと，2頂点間 x, y のコストは c_x \text{ xor } c_y となるため，O(1) で求められる．(LCAを考えると成り立つことが言えます．)

整数の集合から部分集合を選び，xorを最大化する問題になった．（F - Xor Sum 3 にクエリとかがついて少し難しくなった版）xorを \text{mod } 2 の和だと思うと，\mathbb{F}_2 のm-n+1 行 60 列の行列と考えることが出来る．この行列は 10^5 程度の行が存在するが，gauss jordanで基底を求めると高々 60 行まで減少させることができる．

基底を求めたので各桁について1であるような数は高々1つである．下から d 桁目を1にできるならば d より下の桁がどのようになったとしても確実に得する．(2^d \gt 2^{d-1} + 2^{d-2} + \cdots + 2^1 なので) よって，基底のうち大きい方から順に現在の解とxorを取って改善されるならxorを取るという貪欲法で最適解を求めることが出来る．

計算量は

  • DFS木から整数集合をつくるパートが O(M\log W)
  • gauss jordanが O((M+N)(\log W)^2/64)
  • 各クエリについて答えを求めるパートが O(M(\log W)^2)

となる．

bitset<64> bit(x) とすると bit[i] = xの"下から"i桁目 となるのを忘れていて基底の作り方を間違えてハマった

#include <bits/stdc++.h>    
using namespace std;    
using ll = long long;    
using PII = pair<ll, ll>;    
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)    
#define REP(i, n) FOR(i, 0, n)    
#define ALL(x) x.begin(), x.end()    
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }    
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }    
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;    
#ifdef DEBUG_     
#include "../program_contest_library/memo/dump.hpp"    
#else    
#define dump(...)    
#endif    
const ll INF = 1LL<<60;  
  
// GF(2)の行列  
template<int width=64>  
struct matrix {  
    int h, w;  
    vector<bitset<width>> dat;  
    matrix() {}  
    matrix(int h) : h(h), w(width), dat(h) {}  
  
    matrix& operator+=(const matrix& r) {  
        assert(h==r.h && w==r.w);  
        REP(i, h) dat[i] ^= r.dat[i];  
        return *this;  
    }  
    matrix& operator-=(const matrix& r) {  
        assert(h==r.h && w==r.w);  
        REP(i, h) dat[i] ^= r.dat[i];  
        return *this;  
    }  
    matrix& operator*=(const matrix& r) {  
        assert(w==r.h);  
        matrix ret(h, w);  
        REP(i, h) REP(j, r.w) REP(k, w) {  
            ret.dat[i][j] ^= dat[i][k] & r.dat[k][j];  
        }  
        return (*this) = ret;  
    }  
    matrix operator+(const matrix& r) { return matrix(*this) += r; }  
    matrix operator-(const matrix& r) { return matrix(*this) -= r; }  
    matrix operator*(const matrix& r) { return matrix(*this) *= r; }  
    bool operator==(const matrix& a) { return dat==a.dat; }  
    bool operator!=(const matrix& a) { return dat!=a.dat; }  
  
    friend matrix pow(matrix p, ll n) {  
        matrix ret(p.h, p.w);  
        REP(i, p.h) ret.dat[i][i] = 1;  
        while(n > 0) {  
            if(n&1) {ret *= p; n--;}  
            else {p *= p; n >>= 1;}  
        }  
        return ret;  
    }  
    // 階段行列を求める O(HW^2)  
    friend int gauss_jordan(matrix &a) {  
        int rank = 0;  
        REP(i, a.w) {  
            int pivot = -1;  
            FOR(j, rank, a.h) if(a.dat[j][i] != 0) { pivot = j; break; }  
            if(pivot == -1) continue;  
            swap(a.dat[rank], a.dat[pivot]);  
            REP(j, a.h) if(j != rank && a.dat[j][i] != 0) {  
                a.dat[j] ^= a.dat[rank];  
            }  
            rank++;  
        }  
        return rank;  
    }  
  
    friend ostream &operator<<(ostream& os, matrix a) {  
        REP(i, a.h) {  
            REP(j, a.w) os << a.dat[i][j] << " ";  
            os << endl;  
        }  
        return os;  
    }  
};  
  
signed main() {  
    ll n, m, q;  
    cin >> n >> m >> q;  
    vector<vector<PII>> g(n);  
    REP(i, m) {  
        ll a, b, c;  
        cin >> a >> b >> c;  
        g[a].push_back({b, c});  
        g[b].push_back({a, c});  
    }  
  
    ll idx = 0;  
    matrix<64> mat(m-n+1);  
    vector<ll> val(n), depth(n, -1);  
    function<void(ll,ll)> dfs = [&](ll v, ll p) {  
        for(auto to: g[v]) {  
            if(to.first == p) continue;  
            if(depth[to.first] == -1) {  
                depth[to.first] = depth[v] + 1;  
                val[to.first] = val[v] ^ to.second;  
                dfs(to.first, v);  
            } else if(depth[to.first] < depth[v]) {  
                // パス v-to.first と to.second のxor和  
                ll tmp = val[v] ^ val[to.first] ^ to.second;  
                REP(i, 60) mat.dat[idx][i] = !!(tmp & 1LL<<(59-i));   
                idx++;  
            }  
        }  
    };  
    depth[0] = 0;  
    dfs(0, -1);  
      
    ll rank = gauss_jordan(mat);  
  
    REP(i, q) {  
        ll a, b;  
        cin >> a >> b;  
        ll ret = val[a] ^ val[b];  
        REP(j, rank) {  
            ll tmp = 0;  
            REP(k, 60) if(mat.dat[j][k]) tmp |= 1LL<<(59-k);  
            if((ret ^ tmp) > ret) ret ^= tmp;  
        }  
        cout << ret << endl;  
    }  
  
    return 0;  
}

今回のように F_2 行列の幅が高々60程度の場合，bitsetではなくllで持つこともでき，実装をかなり簡潔にできる．

#include <bits/stdc++.h>    
using namespace std;    
using ll = long long;    
using PII = pair<ll, ll>;    
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)    
#define REP(i, n) FOR(i, 0, n)    
#define ALL(x) x.begin(), x.end()    
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }    
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }    
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;    
#ifdef DEBUG_     
#include "../program_contest_library/memo/dump.hpp"    
#else    
#define dump(...)    
#endif    
const ll INF = 1LL<<60;  
  
struct xor_GJ {  
    ll msb(ll v){  
        v |= v >>  1; v |= v >>  2; v |= v >>  4;   
        v |= v >>  8; v |= v >> 16; v |= v >> 32;  
        return v ^ (v >> 1);  
    }  
    vector<ll> A;  
    void add(ll v){  
        for(ll a: A) if(v&msb(a)) v ^= a;  
        if(v) A.push_back(v), sort(ALL(A), greater<>());  
    }  
};  
  
signed main() {  
    ll n, m, q;  
    cin >> n >> m >> q;  
    vector<vector<PII>> g(n);  
    REP(i, m) {  
        ll a, b, c;  
        cin >> a >> b >> c;  
        g[a].push_back({b, c});  
        g[b].push_back({a, c});  
    }  
  
    xor_GJ mat;  
    vector<ll> val(n), depth(n, -1);  
    function<void(ll,ll)> dfs = [&](ll v, ll p) {  
        for(auto to: g[v]) {  
            if(to.first == p) continue;  
            if(depth[to.first] == -1) {  
                depth[to.first] = depth[v] + 1;  
                val[to.first] = val[v] ^ to.second;  
                dfs(to.first, v);  
            } else if(depth[to.first] < depth[v]) {  
                // パス v-to.first と to.second のxor和  
                mat.add(val[v]^val[to.first]^to.second);  
            }  
        }  
    };  
    depth[0] = 0;  
    dfs(0, -1);  
  
    REP(i, q) {  
        ll a, b;  
        cin >> a >> b;  
        ll ret = val[a] ^ val[b];  
        for(auto j: mat.A) if((ret^j) > ret) ret ^= j;  
        cout << ret << endl;  
    }  
  
    return 0;  
}