Hi everyone!

Here's another collection of little tricks and general ideas that might make your life better. Some of them might be well-known to many community members, but I hope they will be useful for someone as well.

Evaluating polynomial modulo $$$p$$$ in all points in $$$O(p \log p)$$$. You can Evaluate $$$P(x)$$$ in every possible $$$x$$$ modulo $$$p$$$ as $$$P(0), P(g^0), P(g^1), \dots, P(g^{p-2})$$$ with chirp Z-transform, where $$$g$$$ is a primitive root modulo $$$p$$$.

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$$$.

Range queries on a plane with Fenwick tree. 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 range updates idea from Petr blog from 2013.

Knapsack on subtrees. We often have dynamic programming on trees that looks like $$$d[v][k]$$$, where $$$v$$$ is the vertex and $$$k$$$ is the number of vertices that are considered for something in the subtree of $$$v$$$. The general transition rule here is something like

where $$$u$$$ is a child of $$$v$$$ and $$$sz[u]$$$ is the size of its subtree. From the way it is written, it looks like the calculation of $$$dp[v][k]$$$ for all valid $$$v$$$ and $$$k$$$ would consume $$$O(n^3)$$$, but, in fact, it consumes $$$O(n^2)$$$ if implemented carefully enough.

This is because the total number of dp iterations is same as total number of pairs of different vertices.

DP on convex subsets.