12tqian's Competitive Programming Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub 12tqian/cp-library

:heavy_check_mark: verify/codeforces/codeforces-1299D.test.cpp

Depends on

Code

#define PROBLEM "https://codeforces.com/contest/1299/problem/D"

#include "../../library/contest/template-short.hpp"
#include "../../library/modular-arithmetic/mod-operations.hpp"
#include "../../library/numerical/xor-basis.hpp"

using namespace ModOperations;

const int N = 1e5 + 5;
const int B = 400;
 
int n, m;
 
vector<vi> store;
 
int comb[B][B];
 
vi add_basis(vi &a, vi &b) {
    vi res;
    each(t, a) {
        add(res, t);
    }
    each(t, b) {
        add(res, t);
    }
    return res;
}
 
bool valid(vector<vi> bs) {
    vi basis;
    each(b, bs) {
        each(x, b) {
            if (!add(basis, x)) return true;
        }
    }
    return false;
}

template <class T> int get_pos(vector<T>& v, T x) { 
    return lower_bound(all(v), x) - v.begin();
}
 
void gen() {
    vector<vi> base = {{}}; // empty basis first

    each(t, base) store.pb(t);
    f1r(i, 1, 6) {
        vector<vi> nbase;
        f0r(j, 32) {
            for (auto t : base) {
                if (add(t, j)) {
                    full_reduce(t);
                    nbase.pb(t);
                }
            }
        }
        base.swap(nbase);
        sort(all(base));
        base.erase(unique(all(base)), base.end());
        each(t, base) {
            store.pb(t);
        }
    }
    sort(all(store));
    f0r(i, sz(store)) {
        auto& x = store[i];
        f0r(j, sz(store)) {
            auto& y = store[j];
            auto z = add_basis(x, y);
            full_reduce(z);
            if (sz(z) != sz(x) + sz(y)) {
                comb[i][j] = -1;
            } else {
                comb[i][j] = get_pos(store, z);
            }
        }
    }
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    gen();
    cin >> n >> m;
    vector<vpi> adj(n);
    vi base(n);
    vi head(n);
    f0r(i, m) {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    vi direct;
    each(t, adj[0]) direct.pb(t.f);
    sort(all(direct));
    vi vis(n);
    vi in(n);
    vi down(n);
    each(go, adj[0]) {
        vis[0] = 1;
        in[0] = -1;
        int x = go.f;
        head[x] = go.s;
        direct.pb(x);
        vi basis;
        int path = 0;
        bool bad = false;
        vi comp;
        int ti = 0;
        function<void(int, int)> dfs = [&](int u, int p) {
            vis[u] = 1;
            comp.pb(u);
            in[u] = ti++;
            down[u] = path;
            each(v, adj[u]) {
                if (v.f == p) continue;
                if (v.f == 0) continue;
                if (vis[v.f]) {
                    if (in[v.f] < in[u]) {
                        if (!add(basis, down[u] ^ down[v.f] ^ v.s)) {
                            bad = true;
                        }
                    }
                    continue;
                }
                path ^= v.s;
                dfs(v.f, u);
                path ^= v.s;
            }
        };
        dfs(x, 0);
        each(t, comp) vis[t] = 0;
        if (bad) base[x] = -1;
        else {
            full_reduce(basis);
            base[x] = get_pos(store, basis);
        } 
    }
    sort(all(direct));
    int sz = sz(direct);
    set<int> rem;
    each(t, direct) {
        rem.insert(t);
    }
    vector<vi> use;
    while (sz(rem)) {
        int x = *rem.begin();
        int ot = -1;
        int w;
        rem.erase(x);
        each(y, adj[x]) {
            if (rem.count(y.f)) {
                ot = y.f;
                w = y.s;
                rem.erase(y.f);
                break;
            }
        }
        vi tmp;
        tmp.pb(0);
        if (ot == -1) {
            if (base[x] != -1) {
                tmp.pb(base[x]);
            }
        } else {
            if (base[x] != -1) {
                tmp.pb(base[x]);
            }
            if (base[ot] != -1) {
                tmp.pb(base[ot]);
            }
            if (base[x] != -1 && base[ot] != -1) {
                int val = head[x] ^ head[ot] ^ w;
                if (val != 0) {
                    int i1 = get_pos(store, {val});
                    int i2 = base[x];
                    int res = comb[i1][i2];
                    if (res != -1) {
                        tmp.pb(res);
                    }
                }
            }
        }
        use.pb(tmp);
    }
    int spaces = sz(store);
    vi dp(spaces);
    vi ndp(spaces);
    dp[0] = 1; 
    each(t, use) {
        each(c, t) {
            f0r(p, spaces) {
                if (comb[c][p] != -1) {
                    madd(ndp[comb[c][p]], dp[p]);
                }
            }
        }
        dp.swap(ndp);
        ndp.assign(spaces, 0);
    }
    int ans = 0;
    each(t, dp) madd(ans, t);
    cout << ans << '\n';
    return 0;
}
#define PROBLEM "https://codeforces.com/contest/1299/problem/D"


#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

namespace ModOperations {

const int MOD = 1e9 + 7;

int mpow(long long b, long long e) {
	long long r = 1;
	while (e) {
		if (e & 1) {
			r *= b; 
			r %= MOD;
		}
		b *= b; 
		b %= MOD;
		e >>= 1;
	}
	return r;
}

int minv(int a) { assert(a); return mpow(a, MOD - 2); }
int add(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
int sub(int a, int b) { a -= b; if (a < 0) a += MOD; return a; }
int mul(int a, int b) { return 1LL * a * b % MOD; }
int divi(int a, int b) { return mul(a, minv(b)); }
int neg(int a) { return a == 0 ? 0 : MOD - a; }
int mod(long long v) { 
	v = int((-MOD < v && v < MOD) ? v : v % MOD); if (v < 0) v += MOD; return v; }
	
int madd(int& a, int b) { return a = add(a, b); }
int msub(int& a, int b) { return a = sub(a, b); }
int mmul(int& a, int b) { return a = mul(a, b); }
int mdivi(int& a, int b) { return a = divi(a, b); }

} // ModOperations

void full_reduce(std::vector<int>& b) {
	int n = (int)b.size();
	for (int i = n - 1; i >= 0; i--) {
		for (int j = i - 1; j >= 0; j--) {
			b[j] = std::min(b[j], b[j] ^ b[i]);
		}
	}
}

template <class T> T reduce(std::vector<T>& b, T x) {
	for (auto& t : b) {
		x = std::min(x, x ^ t);
	}
	return x;
}

template <class T> bool add(std::vector<T>& b, T x) {
	if (!(x = reduce(b, x))) return false;
	int ind = 0;
	while (ind < (int)b.size() && b[ind] > x) ind++;
	b.insert(b.begin() + ind, x);
	return true;
}

using namespace ModOperations;

const int N = 1e5 + 5;
const int B = 400;
 
int n, m;
 
vector<vi> store;
 
int comb[B][B];
 
vi add_basis(vi &a, vi &b) {
    vi res;
    each(t, a) {
        add(res, t);
    }
    each(t, b) {
        add(res, t);
    }
    return res;
}
 
bool valid(vector<vi> bs) {
    vi basis;
    each(b, bs) {
        each(x, b) {
            if (!add(basis, x)) return true;
        }
    }
    return false;
}

template <class T> int get_pos(vector<T>& v, T x) { 
    return lower_bound(all(v), x) - v.begin();
}
 
void gen() {
    vector<vi> base = {{}}; // empty basis first

    each(t, base) store.pb(t);
    f1r(i, 1, 6) {
        vector<vi> nbase;
        f0r(j, 32) {
            for (auto t : base) {
                if (add(t, j)) {
                    full_reduce(t);
                    nbase.pb(t);
                }
            }
        }
        base.swap(nbase);
        sort(all(base));
        base.erase(unique(all(base)), base.end());
        each(t, base) {
            store.pb(t);
        }
    }
    sort(all(store));
    f0r(i, sz(store)) {
        auto& x = store[i];
        f0r(j, sz(store)) {
            auto& y = store[j];
            auto z = add_basis(x, y);
            full_reduce(z);
            if (sz(z) != sz(x) + sz(y)) {
                comb[i][j] = -1;
            } else {
                comb[i][j] = get_pos(store, z);
            }
        }
    }
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    gen();
    cin >> n >> m;
    vector<vpi> adj(n);
    vi base(n);
    vi head(n);
    f0r(i, m) {
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }
    vi direct;
    each(t, adj[0]) direct.pb(t.f);
    sort(all(direct));
    vi vis(n);
    vi in(n);
    vi down(n);
    each(go, adj[0]) {
        vis[0] = 1;
        in[0] = -1;
        int x = go.f;
        head[x] = go.s;
        direct.pb(x);
        vi basis;
        int path = 0;
        bool bad = false;
        vi comp;
        int ti = 0;
        function<void(int, int)> dfs = [&](int u, int p) {
            vis[u] = 1;
            comp.pb(u);
            in[u] = ti++;
            down[u] = path;
            each(v, adj[u]) {
                if (v.f == p) continue;
                if (v.f == 0) continue;
                if (vis[v.f]) {
                    if (in[v.f] < in[u]) {
                        if (!add(basis, down[u] ^ down[v.f] ^ v.s)) {
                            bad = true;
                        }
                    }
                    continue;
                }
                path ^= v.s;
                dfs(v.f, u);
                path ^= v.s;
            }
        };
        dfs(x, 0);
        each(t, comp) vis[t] = 0;
        if (bad) base[x] = -1;
        else {
            full_reduce(basis);
            base[x] = get_pos(store, basis);
        } 
    }
    sort(all(direct));
    int sz = sz(direct);
    set<int> rem;
    each(t, direct) {
        rem.insert(t);
    }
    vector<vi> use;
    while (sz(rem)) {
        int x = *rem.begin();
        int ot = -1;
        int w;
        rem.erase(x);
        each(y, adj[x]) {
            if (rem.count(y.f)) {
                ot = y.f;
                w = y.s;
                rem.erase(y.f);
                break;
            }
        }
        vi tmp;
        tmp.pb(0);
        if (ot == -1) {
            if (base[x] != -1) {
                tmp.pb(base[x]);
            }
        } else {
            if (base[x] != -1) {
                tmp.pb(base[x]);
            }
            if (base[ot] != -1) {
                tmp.pb(base[ot]);
            }
            if (base[x] != -1 && base[ot] != -1) {
                int val = head[x] ^ head[ot] ^ w;
                if (val != 0) {
                    int i1 = get_pos(store, {val});
                    int i2 = base[x];
                    int res = comb[i1][i2];
                    if (res != -1) {
                        tmp.pb(res);
                    }
                }
            }
        }
        use.pb(tmp);
    }
    int spaces = sz(store);
    vi dp(spaces);
    vi ndp(spaces);
    dp[0] = 1; 
    each(t, use) {
        each(c, t) {
            f0r(p, spaces) {
                if (comb[c][p] != -1) {
                    madd(ndp[comb[c][p]], dp[p]);
                }
            }
        }
        dp.swap(ndp);
        ndp.assign(spaces, 0);
    }
    int ans = 0;
    each(t, dp) madd(ans, t);
    cout << ans << '\n';
    return 0;
}
Back to top page