CSES - KILO 2018 0/5 - Useful information

bitwise operators

Xor, denoted by \oplus of two bits a and b is 1 if exactly one of the bits is 1, and 0 otherwise.

0 \oplus 0 = 0
0 \oplus 1 = 1 \text{ mod } p
1 \oplus 0 = 1
1 \oplus 1 = 0

The bitwise XOR a \oplus b of two nonnegative integers a = \sum_{i = 0}^{k} a_{i} 2^{i} and b = \sum_{i = 0}^{k} b_{i} 2^{i} where a_{i}, b_{i} \in \{0, 1\} for all i, is defined as a \oplus b = \sum_{i = 0}^{k} (a_{i} \oplus b_{i}) 2^{i}. That is, we just apply the xor-operation bitwise to the bit representations of a and b. For example:

10 \oplus 6 = 12
7 \oplus 11 = 12
12 \oplus 0 = 12

1010 is the binary representation of 10.
0110 is the binary representation of 6
1100 is the binary representation of 12 = 10 \oplus 6.

A useful property of xor is that it is it's own inverse function. That means that a \oplus b = c \iff a = c \oplus b.

The other two bitwise binary operators are bitwise AND \mathrel{\&}, and bitwise OR \mathrel{|}.

In bitwise AND, a bit is one if both input operands have it as one. In bitwise OR, a bit is one if either or both of the input operands have it as one. For example:

10 \mathrel{\&} 6 = 2
10 \mathrel{|} 6 = 14

Often in competitive programming problems where xor and other bitwise operators appear, you should be looking to do things one bit at a time, since the value of a bit doesn't affect the values of other bits. Then you only have to handle the case where every integer is either zero or one.

In C, C++, Python and Java,

The bitwise xor-operator is '^'
The bitwise and-operator is '&'
The bitwise or-operator is '|'

modulo-operation

a \text{ mod } b, where a and b are integers, and b > 0 is defined as the remainder when a is divided by b, more specifically, as a - \left\lfloor a / b \right\rfloor \cdot b. For example:

100 \text{ mod } 3 = 1
67 \text{ mod } 100 = 67
a \text{ mod } a = 0 for all a > 0.

In many competitive programming problems, you are asked to output the answer mod 10^{9} + 7. This is because the answer could be very large, and working with large integers is hard and often not very interesting. The reason why this particular integer is used, is because it's a prime, it's very easy to remember, and 2 \cdot (10^{9} + 7) fits to the integer type in C / C++ / Java.

The modulo-operation has many properties that you should know. For example,

(a \cdot b) \text{ mod } p = ((a \text{ mod } p) \cdot (b \text{ mod } p)) \text{ mod } p
(a + b) \text{ mod } p = ((a \text{ mod } p) + (b \text{ mod } p)) \text{ mod } p

The modulo-operator is '%' in C, C++, Python and Java.

gcd-function

We say that an integer b divides another integer a if a / b is an integer.

The gcd(a, b) of numbers a, b where not both of a and b are zero is defined as the maximum integer that divides both of them. For example:

gcd(24, 30) = 6
gcd(15, 28) = 1
gcd(a, 0) = a for all a > 0

gcd can be calculated the following way:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

This is called the euclidean algorithm. The euclidean algorithm can also be used to find integers x, y such that ax + by = gcd(a, b). This algorithm is called the extended euclidean algorithm. In code, it looks like this:

// Returns a triple {gcd(a, b), x, y}
vector<int> extEuc(int a, int b) {
    if (b == 0) return {a, 1, 0};
    int k = a / b; // Division in C++ rounds down. a % b = a - (a/b) * b.
    vector<int> sub = extEuc(b, a - k * b);
    return {sub[0], sub[2], sub[1] - k * sub[2]};
}

fast exponentation

Often you need to calculate a^{b} \text{ mod } p with large b. Two identities help us with this:

If b \text{ mod } 2 = 0, a^{b} = (a^{b / 2})^{2}
If b \text{ mod } 2 = 1, a^{b} = a \cdot a^{b - 1}

Repeatedly using these two identities, while making sure we don't overflow, gives us a O(log(b)) algorithm for finding a^{b} \text{ mod } p:

int modPow(int a, int b, int p) {
    if (b == 0) return 1;
    if (b % 2 == 1) return ((long long)a * modPow(a, b-1, p)) % p;
    long long sub = modPow(a, b / 2, p);
    return (sub * sub) % p;
}

modular inverse

The modular inverse a^{-1} \text{ mod } p is the unique integer such that a \cdot a^{-1} \text{ mod } p = 1. It exists iff gcd(a, p) = 1.

If p is prime, for all a \neq 0, a^{p-1} \text{ mod } p = 1. This is called fermat's little theorem. This is useful, since 1 = a^{p-1} \text{ mod } p = a \cdot a^{p-2} \text{ mod } p = a \cdot a^{-1} \text{ mod } p = 1. This means that a^{p-2} is the modular inverse of a mod p.

// Modular inverse. p must be prime and a mod p must be nonzero
int modInv(int a, int p) {
    return modPow(a, p-2, p);
}

If p is not prime, we can use the extended euclidean algorithm to find a's inverse. Let's find x and y such that ax + py = gcd(a, p) = 1. This implies that ax = 1 - py. Taking mod p from both sides gives ax \text{ mod } p = 1. Therefore x is the modular inverse of a.

// Modular inverse. gcd(a, p) = 1 must hold.
int modInv(int a, int p) {
    vector<int> vec = extEuc(a, p);
    return vec[1] % p;
}

rational numbers mod p

In some competitive programming problems, the answer is not an integer, but instead a rational number. There are two ways to deal with this:

Ask the output as a double with given precision
Ask the output as a rational number

The problem with approach one is that some algorithms have numerical inprecision, and handling that is both very hard and not interesting.

The problem with approach two is that the integers in the divisor and dividend might be very large, so this approach would force us to work with large integers, which is again both hard and not interesting.

The solution is to use rational numbers mod p, where p is a prime. Define f(x) as a function that turns the rational number x into a integer mod p. More specifically, If a / b is a reduced fraction, and b \text{ mod } p \neq 0, we define f(a / b) = a \cdot b^{-1} \text{ mod } p.

Note that ak \cdot (bk)^{-1} \text{ mod } p = a \cdot b^{-1} \text{ mod } p if k \text{ mod } p \neq 0. Therefore you don't need the fraction to be reduced to find f(a / b), you just need that b \text{ mod } p \neq 0.

Working with fractions in this form is easy:

f(a / b) + f(c / d) = f(a / b + c / d)
f(a / b) + f(c / d) = f(a / b \cdot c / d)

Since if a \text{ mod } p \neq 0 and b \text{ mod } p \neq 0, then ab \text{ mod } p \neq 0, and a / b + c / d = (ad + bc) / bd, there are no problems with the divisor becoming 0 mod p.

KILO 2018 0/5