General ideas (a bit more of them)

Правка en3, от adamant, 2022-07-03 05:29:53

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

$$$ a^k \equiv a^{\phi(m) + k \mod \phi(m)} \pmod m, $$$

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

$$$ s_{xy} \mapsto s_{xy} + (x-a+1)(y-b+1)c, $$$

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

$$$ s_{xy} = s_{xy}^{(0)}+ x \cdot s_{xy}^{(x)} + y \cdot s_{xy}^{(y)} + xy \cdot s_{xy}^{(xy)}, $$$

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

$$$\begin{align} s_{xy}^{(0)} &\mapsto s_{xy}^{(0)} + (a-1)(b-1)c, \\ s_{xy}^{(x)} &\mapsto s_{xy}^{(x)} - (b-1)c, \\ s_{xy}^{(y)} &\mapsto s_{xy}^{(y)} - (a-1)c, \\ s_{xy}^{(xy)} &\mapsto s_{xy}^{(xy)} + c. \end{align}$$$
code

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

$$$ d[v][k] = \sum\limits_{t=1}^{sz[u]} f(d[v][k - t], d[u][t]), $$$

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.

Теги tutorial, i love tags

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский adamant 2022-07-03 20:43:38 82
en22 Английский adamant 2022-07-03 20:40:31 134
en21 Английский adamant 2022-07-03 20:37:28 1210
en20 Английский adamant 2022-07-03 20:19:36 1
en19 Английский adamant 2022-07-03 20:19:06 412
en18 Английский adamant 2022-07-03 18:18:14 1141
en17 Английский adamant 2022-07-03 17:04:12 6
en16 Английский adamant 2022-07-03 17:00:10 38
en15 Английский adamant 2022-07-03 16:51:22 616
en14 Английский adamant 2022-07-03 16:42:16 132
en13 Английский adamant 2022-07-03 16:30:11 14
en12 Английский adamant 2022-07-03 16:29:39 95
en11 Английский adamant 2022-07-03 16:28:28 13
en10 Английский adamant 2022-07-03 16:27:46 60
en9 Английский adamant 2022-07-03 16:22:40 0 (published)
en8 Английский adamant 2022-07-03 16:22:25 1096
en7 Английский adamant 2022-07-03 16:04:31 55
en6 Английский adamant 2022-07-03 15:52:24 46
en5 Английский adamant 2022-07-03 15:15:04 9278
en4 Английский adamant 2022-07-03 06:00:44 2099
en3 Английский adamant 2022-07-03 05:29:53 956
en2 Английский adamant 2022-07-03 05:02:53 2774 Tiny change: 'e with $m$ and $k > ' -> 'e with $m$, and $k > '
en1 Английский adamant 2022-07-03 02:59:55 412 Initial revision (saved to drafts)