Sets the kth bit of x to 0 and returns the result

add x to a[i], basically the change occurs for all t[n][i] where n is a candidate node so we just create a lazy array to remember the change for each

add val in all the values from a[qL] to a[qR] positions

range maximize query

range minimize query

returns 1e9 if the point is on the polygon

returns 1e9 if the point is on the polygon

par = parity of the number of kth bits which are on f = if we have offed any kth bit

sum of i1 * i2 * ... ik s.t. 0 <= i1 < i2 < ... < ik <= n O(k^2 log n), can be optimized to O(k logk logn)

number of ways to select k linearly independant vectors of length n mul(q^n - q^i) over 0 <= i < k

finds the determinant of (a - xI) in O(n^2), here a is a hessenberg matrix

up / down = sum_{i=l}^{r}{1/(1-a[i]*x)}

Given a polynomial of degree k, f(x) = \sum_{i = 0}^{k}{c_i * x^i} and c_k != 0 Let S(n) = \sum_{i = 0}^{n}{a^i * f(i)} Given S(0), S(1), ... S(k) fin

number of solutions of the equation x_0 + ... + x_(n-1) = s s.t. 0 <= x_i <= a_i O(2^(n/2)*n^2)

a[k] = c[0] * a[k - 1] + c[1] * a[k - 2] + ... for k >= n

ans[n] = \sum_{i = 0}^{n-1}{ans[i] * a[n - i]}

ans[i] = number of partitions of i O(n sqrt(n)) takes 1.5s for n = 5e5

returns the number of distinct values of (a^k % n) over all integers a

no memorization needed! sum of f(i) s.t. spf[i] > primes[j]

number of solutions to ax + by + cz = n s.t. x, y, z >= 0 a, b, c >= 1 O(log(max(a, b, c))); paper: https://cs.uwaterloo.ca/journals/JIS/VOL23/Binner/

mul (1 - ix)

returns the number of solutions to the equation x_1 + x_2 + ... + x_n = s and 0 <= l <= x_i <= r

returns the number of solutions to the equation x_0 + ... + x_(n-1) = s s.t. 0 <= x_i <= a_i O(2^(n/2)*n^2)

if x >= log2(m), then a^x = a^(MOD(x, phi(m))) % m

O((max number of divisors of a[i]) * n * log(max a[i])) but faster in practice lcm(a1, a2, ... an) = lcm(lcm(a1, ..., a[n-1]), an) = lcm(a1, ...,

An element Z[i] of Z array stores length of the longest substring starting from str[i] which is also a prefix of str[0..n-1]. The first entry of Z arr

Every input vector must need to be of size 1<<B z(f(s))=\sum_{s' $ s}{f(s')} O(B * 2 ^ B) zeta transform is actually SOS DP

each string contains 'a' and 'b'

initial time