Art of XOR

We won’t mention linear base in this article.

Table of Contents

  1. Overview
    1. Some properties
  • BZOJ 3329 Xorequ. Subtask 1
    1. Description
    2. Solution
  • Codeforces 1039 C Network Safety
    1. Description
    2. Solution
  • Codeforces 1016 D Vasya And The Matrix
    1. Description
    2. Solution

    • Overview

    Some properties

    • Commutativity: $a\,\oplus\,b = b\,\oplus\,a$
    • Associativity: $a\,\oplus(b\,\oplus\,c) = (a\,\oplus\,b)\,\oplus\,c$
    • Distributivity(only for logical conjunction): $ c \wedge\, (a\,\oplus\,b) = (c \wedge a) \oplus (c\wedge b)$
    • Self-Reflexivity: $a\,\oplus\,b\,\oplus\,b = a\,\oplus\,0 = a$
    • A Corollary: $a\,\oplus\,b = c \rightarrow a\,\oplus\,c = b$

    BZOJ 3329 Xorequ. Subtask 1

    Description

    Evaluate how many numbers $x$ satisfies that $x\,\oplus\,3x=2x$, for $x \le n$

    Solution

    Because of the Corollary above, we can get: $x\,\oplus\,2x = 3x$.

    Split $3x$ into $x + 2x$, \’cause $2x = x << 1$, if there\’re $1$s on the same positions of both $x$ and $2x$\’s binary representation, the add operation ans xor operation would lead to different results! (e.g. $(1)_2 + (1)_2 = (10)_2$, while $(1)_2\,\oplus\,(1)_2 = (0)_2$).

    i.e. for each legal $x$, there’s no consecutive 1s in its binary representation.

    Use DP for Digit to deal with it.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>

    using namespace std;

    typedef long long ll;

    const int p = 1e+9 + 7;

    int bin[70], tot;
    ll f[70][2];
    ll n;

    ll dfs(int p, int a, bool z, bool u)
    {
    	if(!p) return 1;
    	if(~f[p][a] && !u && !z) return f[p][a];
    	int lim = u ? bin[p] : 1; ll tot = 0;
    	for(int i = 0; i <= lim; ++i)
    	{
    		if(a && i) continue;
    		tot += dfs(p - 1, i, (z && (!i)), (u && (i == bin[p])));
    	}
    	if(!z && !u) f[p][a] = tot;
    	return tot;
    }
    ll solve1(ll u)
    {
    	memset(f, -1, sizeof f);
    	tot = 0;
    	while(u)
    	{
    		bin[++tot] = (u&1);
    		u >>= 1;
    	}
    	return dfs(tot, 0, 1, 1);
    }

    int main()
    {
    	int T;
    	scanf("%d", &T);
    	while(T--)
    	{
    		scanf("%lld", &n);
    		printf("%lld\n", solve1(n) - solve1(0));
    		//solu2::main(n + 2);
    	}
    	
    	return 0;
    }

    Codeforces 1039 C Network Safety

    Description

    Given some points with value $c_i$ range from $0$ to $2^k - 1$, and some edges link them.

    We say an edge is Safe if and only if the two points it connects have distinct values.

    A kind of Virus with value $x$ is now invading the network and if a point is infected, its value changes from $c_i$ to $c_i\,\oplus\,x$. Then some of edges would be unsafe.

    Evaluate the number of pairs $(A,x)$, where $A$ is a subset of points($|A| \ge 0$), and $x$ is the value of virus ranging from $0$ to $2^k-1$, if all points in $A$ were infected while no others were done so, the rest of the network remains safe.

    Solution

    First consider a pair of points with values $a, b$.

    If $x = a\,\oplus\,b$, then this edges would turn unsafe, but lead to no effects on other points.

    Thus we can put $v_i\,\oplus\,v_j$ on edge connecting $i, j$. And for each kind of edges\’ value $w_i$, we can calculate number of connected components, take any subset of these components and $w_i$ as a pair, the rest of the network wouldn’t suffer any invasion.

    Use a Union-Find Set to maintain it.

    Finally, for $x$ doesn’t exist in set $W$, we can take any subset of the whole graph.

    Note that, refresh the parent array in $O(n)$ time will get TLE. However, use trick in code below will AC, Though it is ugly.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <map>
    #include <cctype>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>

    using std::unordered_map;
    using std::vector;
    using std::cerr;
    using std::cout;
    using std::endl;
    using std::fill;
    using std::min;
    using std::unordered_set;

    typedef long long ll;

    const ll mod = 1e+9 + 7;
    const int maxn = 5e+5 + 5;

    struct edge
    {
    	ll frm, to;
    	edge(ll f_ = 0, ll t_ = 0):frm(f_),to(t_){}
    };
    ll n, m, k;
    ll ans, c[maxn];
    unordered_map<ll, vector<edge> > e_mp;
    unordered_map<ll, ll> f;

    ll find(ll x) {return (!f.count(x) || f[x] == x) ? x : f[x] = find(f[x]);}

    inline ll quick_power(ll base, ll index)
    {
    	ll ret = 1;
    	while(index)
    	{
    		if(index & 1) ret = (ret * base) % mod;
    		index >>= 1;
    		base = base * base % mod;
    	}
    	return ret % mod;
    }

    int main()
    {
    	scanf("%I64d%I64d%I64d", &n, &m, &k);
    	for(ll i = 1; i <= n; ++i) scanf("%I64d", &c[i]);
    	for(ll i = 1; i <= m; ++i)
    	{
    		ll u, v;
    		scanf("%I64d%I64d", &u, &v);
    		ll x = (c[u] ^ c[v]);
    		e_mp[x].push_back(edge(u,v));
    	}
    	for(auto vec : e_mp)
    	{
    		f.clear(); unordered_set<ll> dsu;
    		for(auto pr : vec.second)
    		{ 
    			ll fx = find(pr.frm), fy = find(pr.to);
    			if(fx < fy) f[fy] = fx;
    			else f[fx] = fy;
    			dsu.insert(pr.frm); dsu.insert(pr.to);
    		}
    		ll single_p = dsu.size(); dsu.clear();
    		for(auto pr : vec.second)
    			dsu.insert(find(min(pr.frm, pr.to)));
    		ans = (ans + quick_power(2ll, dsu.size()+n-single_p)) % mod;
    	}
    	ans = ans + quick_power(2ll, n) * (quick_power(2ll, k) - e_mp.size());
    	ans = (ans % mod + mod) % mod;
    	cout << ans << endl;
    	return 0;
    }

    Codeforces 1016 D Vasya And The Matrix

    Description

    Consider a $n \times m$ matrix, given every line and every column\’s xor sum.

    Construct a matrix satisfying the restriction if could, otherwise output No.

    Solution

    If we xor all given numbers together, every element in the matrix will be calculated twice, thus the result is legal if and only if it equals to $0$.

    Then how to construct it?

    Since the matrix is correct, we can construct it in any way we want. To make each column $j$ from $2$ to $m$ results in $b_j$, we can simply make $c_{1,j} = b_j$. Lines from $2$ to $n$ is the same. Then $c_{1,1}$ must be $a_1 \oplus b_2 \oplus \ldots \oplus b_m$. The rest of the matrix is $0$.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>

    using namespace std;

    typedef long long ll;

    const int maxn = 105;

    int n, m;
    ll ans, line[maxn], col[maxn];

    int main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr); cout.tie(nullptr);

    	cin >> n >> m;
    	for(int i = 1; i <= n; ++i) cin >> line[i], ans ^= line[i];
    	for(int i = 1; i <= m; ++i) cin >> col[i], ans ^= col[i];
    	if(ans)
    	{
    		cout << "NO" << endl;
    		return 0;
    	}
    	else
    	{
    		
    		cout << "YES" << endl;
    		ll fir = line[1]; for(int i = 2; i <= m; ++i) fir ^= col[i];
    		cout << fir << " ";
    		for(int i = 2; i <= m; ++i) cout << col[i] << " ";
    		cout << endl;
    		for(int i = 2; i <= n; ++i)
    		{
    			cout << line[i] << " ";
    			for(int j = 2; j <= m; ++j) cout << "0 ";
    			cout << endl;
    		}
    	}
    	return 0;
    }