Hi everyone!

Here's another collection of little tricks and general ideas that might make your life better (or maybe worse).

1. Evaluating polynomial modulo small prime $$$p$$$. Given a polynomial $$$q(x)$$$, you may evaluate it modulo $$$p$$$ in all possible arguments. To do this, compute $$$q(0)$$$ separately and use chirp Z-transform to compute $$$q(g^0), q(g^1), \dots, q(g^{p-2})$$$, where $$$g$$$ is a primitive root modulo $$$p$$$.

2. Generalized Euler theorem. Let $$$a$$$ be a number, not necessarily co-prime with $$$m$$$, and $$$k > \log_2 m$$$. Then

where $$$\phi(m)$$$ is Euler's totient. This follows from the Chinese remainder theorem, as it trivially holds for $$$m=p^d$$$.

This fact can be used in 906D - Power Tower.

3. Range add/range sum in 2D. Fenwick tree, generally, allows for range sum/point add queries.

Let $$$s_{xy}$$$ be a sum on $$$[1,x] \times [1,y]$$$. If we add $$$c$$$ on $$$[a, +\infty) \times [b, +\infty)$$$, the sum $$$s_{xy}$$$ would change as

for $$$x \geq a$$$ and $$$y \geq b$$$. To track these changes, we may represent $$$s_{xy}$$$ as

which allows us to split the addition of $$$c$$$ on $$$[a,+\infty) \times [b,+\infty)$$$ into additions in $$$(a;b)$$$:

const int maxn = 1e3 + 42;

int S[4][maxn][maxn];

void add_point(int z, int x, int Y, int c) {
    for(; x < maxn; x += x & -x) {
        for(int y = Y; y < maxn; y += y & -y) {
            S[z][x][y] += c;
        }
    }
}

// add c on [a, inf) x [b, inf)
void add_suffix(int a, int b, int c) {
    add_point(0, a, b, c);
    add_point(1, a, b, -c * (a - 1));
    add_point(2, a, b, -c * (b - 1));
    add_point(3, a, b, c * (a - 1) * (b - 1));
}

// add c on [x1, x2) x [y1, y2)
void add_range(int x1, int y1, int x2, int y2, int c) {
    add_suffix(x1, y1, c);
    add_suffix(x1, y2, -c);
    add_suffix(x2, y1, -c);
    add_suffix(x2, y2, c);
}

int get_point(int z, int x, int Y) {
    int res = 0;
    for(; x > 0; x -= x & -x) {
        for(int y = Y; y > 0; y -= y & -y) {
            res += S[z][x][y];
        }
    }
    return res;
}

// get sum on [0, x] x [0, y]
int get_prefix(int x, int y) {
    return get_point(0, x, y) * x * y 
         + get_point(1, x, y) * y
         + get_point(2, x, y) * x 
         + get_point(3, x, y);
}

// get sum on (x1, x2] x (y1, y2]
int get_range(int x1, int y1, int x2, int y2) {
    return get_prefix(x2, y2)
         - get_prefix(x1, y2) 
         - get_prefix(x2, y1) 
         + get_prefix(x1, y1);
}

The solution generalizes 1-dimensional Fenwick tree range updates idea from Petr blog from 2013.

4. DP on convex subsets. You want to compute something related to convex subsets of a given set of points in 2D space.

You sort points over bottom-left point $$$O$$$, then over point $$$B$$$ and go through all pairs $$$(A, C)$$$ with two pointers

This can be done with dynamic programming, which generally goes as follows:

1. Iterate over possible bottom left point $$$O$$$ of the convex subset;
2. Ignore points below it and sort points above it by angle that they form with $$$O$$$;
3. Iterate over possible point $$$B$$$ to be the "last" in the convex subset. It may only be preceded by a point that was sorted before it and succeeded by a points that was sorted after it when the points were sorted around $$$O$$$;
4. Sort considered points around $$$B$$$, separately in "yellow" and "green" areas (see picture);
5. Iterate over possible point $$$C$$$ which will succeed $$$B$$$ in the convex subset;
6. Set of points that may precede $$$B$$$ with a next point $$$C$$$ form a contiguous prefix of points before $$$B$$$;
7. The second pointer $$$A$$$ to the end of the prefix is maintained;
8. Eventually, for every $$$B$$$, all valid pairs of $$$A$$$ and $$$C$$$ are iterated with two pointers.

This allows to consider in $$$O(n^3)$$$ all the convex subsets of a given set of points, assuming that sorting around every point $$$B$$$ was computed beforehand in $$$O(n^2 \log n)$$$ and is now used to avoid actual second sorting of points around $$$B$$$.

5. Knapsack on segments. You're given $$$a_1, \dots, a_n$$$ and need to answer $$$q$$$ queries. Each query is whether $$$a_l, a_{l+1}, \dots, a_r$$$ has a subset of sum $$$w$$$. This can be done with dynamic programming $$$L[r][w]$$$ being the right-most $$$l$$$ such that $$$a_l, \dots, a_r$$$ has a subset with sum $$$w$$$:

6. Data structure with co-primality info. There is a structure that supports following queries:

1. Add/remove element $$$x$$$ from the set, all prime divisors of $$$x$$$ are known;
2. Count the number of elements in the structure that are co-prime with $$$x$$$.

Without loss of generality, we may assume that the numbers are square-free.

Let $$$w(x)$$$ be the number of distinct prime divisors of $$$x$$$ and $$$N_x$$$ be the amount of numbers divisible by $$$x$$$ in the structure. When $$$x$$$ is added or removed from the structure, you need to update $$$2^{w(x)}$$$ values of $$$N_x$$$. Now, having $$$N_x$$$, how to count numbers co-prime with $$$x$$$?

where $$$\mu(d)$$$ is the Möbius function. This formula essentially uses inclusion-exclusion principle, as $$$N_d$$$ counts numbers divisible by $$$d$$$ and we need to count numbers that are not divisible by any divisor of $$$x$$$.

The method was used in 102354B - Yet Another Convolution.

7. Generalized inclusion-exclusion. Let $$$A_1, \dots, A_n$$$ be some subsets of a larger set $$$S$$$. Let $$$\overline{A_i} = S \setminus A_i$$$.

With the inclusion-exclusion principle, we count the number of points from $$$S$$$ that lie in neither of $$$A_i$$$:

assuming the empty intersection to be the full set $$$S$$$. We may split the formula half-way as

This way, we're able to count the number of points from $$$S$$$ that lie in exactly $$$r$$$ set among $$$A_1, \dots, A_n$$$.

Explanation lies in the fact that for a fixed $$$Y$$$, we may use PIE directly:

then if summing up over all possible $$$Y$$$, each set $$$X$$$ will always have $$$(-1)^{m-r}$$$ coefficient and will occur for $$$\binom{m}{r}$$$ sets $$$Y$$$.

8. Finding roots of polynomials over $$$\mathbb Z_p$$$. You're given $$$q(x)$$$. You want to find all $$$a \in \mathbb Z_p$$$, such that $$$q(a)=0$$$.

This is done in two steps. First, you compute

to get rid of non-linear or repeated linear factors of $$$q(x)$$$, as

Second, you pick random $$$a$$$ and compute

This will filter roots of $$$h(x)$$$ by whether they're quadratic residues if $$$a$$$ is added to them or not.

Quadratic residues make up $$$\frac{p-1}{2}$$$ of numbers in $$$\mathbb Z_p$$$ and are distributed uniformly, so you'll have at least $$$\frac{1}{2}$$$ chance to get non-trivial divisor of $$$h(x)$$$. This is particularly useful when you want to solve e.g. $$$x^2 \equiv a \pmod p$$$, which can be done in $$$O(\log p)$$$ with this algorithm.

The method is called Berlekamp–Rabin algorithm and can be generalized to find all factors of $$$q(x)$$$ over $$$\mathbb Z_p$$$ (see this comment).

9. Matching divisible by $$$m$$$. You're given a weighted bipartite graph and you need to check if there exists a perfect matching that sums up to the number that is divisible by $$$m$$$. In other words, whether there exists a permutation $$$\sigma_1, \dots, \sigma_n$$$ such that

For this, we introduce matrices $$$R^{(0)}, \dots, R^{(m-1)}$$$ such that

where $$$A_{ij}$$$ is weight between $$$i$$$ in the first part and $$$j$$$ in the second part, $$$x_{ij}$$$ is a random number when there is an edge between $$$i$$$ and $$$j$$$ or $$$0$$$ otherwise, and $$$\omega$$$ is a root of unity of degree $$$m$$$. The determinants of such matrices is then

where $$$N(\sigma)$$$ is a parity of $$$\sigma$$$. If you sum them up, you get

But at the same time,

Thus, a summand near $$$\sigma_1, \dots, \sigma_n$$$ will be non-zero only if $$$A_{1\sigma_1} + \dots + A_{n \sigma_n}$$$ sums up to the number divisible by $$$m$$$.

Therefore, the property can be checked in $$$O(mn^3)$$$.

The method was used in CSAcademy — Divisible Matching.