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, n] \times [b, m]$$$, 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,n] \times [b,m]$$$ into additions in $$$(a;b)$$$:
The solution generalizes 1-dimensional Fenwick range updates idea from Petr blog from 2013.