Learning Notes on Multiplicative Functions, Dirichlet Convolution, Mobius Inversion, etc

Common Functions
  • Unit Function: $\epsilon(n)=[n=1]$
  • Constant Function: $1(n)=1$
  • Euler Function: $\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]$
  • Mobius Function:$ \mu(n)=\left\{
    1 & \text{, if $n=1$} \\
    0 & \text{, if $n$ has some square}\\
    (-1)^k & \text{, ($k$ is the number of prime divisors of $n$) otherwise}
Dirichlet Convolution

$$ (f*g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) $$

Common Convolutions:
$$ \varepsilon=\mu * 1 \iff \varepsilon(n)=\sum_{d\mid n}\mu(d)$$ $$ d=1 * 1 \iff d(n)=\sum_{d\mid n}1 $$ $$ \sigma=d * 1 \iff \sigma (n)=\sum_{d\mid n}d$$ $$\varphi=\mu * \text{ID} \iff \varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d})$$

Mobius Inversion

The first form of Mobius Inversion:
$\displaystyle F(n)=\sum_{d|n}f(d)\implies f(n)=\sum_{d|n}\bigg(\mu(d)\cdot F\Big(\frac{n}{d}\Big)\bigg)$

Proof of the first form:
$\displaystyle \sum_{d|n}\bigg(\mu(d)\cdot F\Big(\frac{n}{d}\Big)\bigg)$ $=\sum_{d|n}\bigg(\mu(d)\cdot \sum_{k|\frac{n}{d}}f(k)\bigg)=\sum_{k|n}\bigg(f(k)\cdot \sum_{d|\frac{n}{k}}\mu(d)\bigg)=f(n)$

Second form:
$\displaystyle F(n)=\sum_{n|d}f(d)\implies f(n)=\sum_{n|d}\bigg(\mu\Big(\frac{d}{n}\Big)\cdot F(d)\bigg)$

Related Problems

Euler’s Functions/ Mobius Inversion: CF645F
Let $F[n]$($f[n]$) be the number of $k$-tuples the g.c.d. of whose numbers is a multiple of k (exactly k ), respectively. First we have $F[n] = {{cnt[n]}\choose{k}}$, where $cnt[n]$ is the number of species that has number divisible by $n$.
By Mobius Inversion, we have $f(d) = \sum_{d|n} \mu(\frac{n}{d}) F(n)$, and the answer for the problem equals $\sum_{d = 1}^{10^6} d \cdot f(d)$
$$= \sum_{d = 1}^{10^6} d \cdot \sum_{d|n} \mu(\frac{n}{d}) F(n) $$
We can change the summation to sum over $n$ instead, and then we have $$= \sum_{n = 1}^{10^6} \sum_{d|n} d \cdot \mu(\frac{n}{d}) F(n)$$ $$= \sum_{n = 1}^{10^6} F(n) \sum_{d|n} d \cdot \mu(\frac{n}{d}) $$ $$= \sum_{n = 1}^{10^6} F(n) \varphi(n)$$.
Therefore, each update can only affect $O(maxdivs)$ values of $F$, which is good enough for this problem.

Changing representation of the sequence: 1097F
In this problem, we can store the frequency of the multiples instead of the number itself. This is essentially Mobius Inversion, which is also a linear transformation, we can use bitwise xor for addition, and bitwise and for Cartisian product.

Key takeaways:
1. The formula $lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$ can turn the problem to some gcd-related stuff where we can apply Mobius Inversion.

No. of Divisors: CF235E
Let $d(x)$ be the number of divisors of $x$.
Then $ d(mn)=\sum\limits_{i|m}\sum\limits_{j|n}[(i,j)=1] $
Also, $d(r \cdot s \cdot t)=\sum\limits_{i|r}\sum\limits_{j|st}[(i,j)=1]=\sum\limits_{i|r}\sum\limits_{j|s}\sum\limits_{k|t}[(i,jk)=1][(j,k)=1]$ $=\sum\limits_{i|r}\sum\limits_{j|s}\sum\limits_{k|t}[(i,j)=1][(i,k)=1][(j,k)=1]$
Refer to this blog for more details.

Centroid Decomposition: CF809E
By enumerating the GCD, we need to calculate $$\sum_{i = 1}^{n} \frac{f_i \cdot i}{\varphi(i)}$$ where $$f_i = \sum_i \sum_j [(a_i, b_j) = g] \varphi (a_i) \varphi (b_j) d(i)$$. Instead of calculating $f_i$, we can calculate $g_d = \sum_{d | a_i} \sum_{d | b_j} \varphi (a_i) \varphi (b_j) d(i) $ by using centroid decomposition.

Total number of divisors of all the numbers is $O(n \log n)$ and each of them is used $O(\log n)$ because of centroid decomposition. So the total complexity is $O(n \log^2 n)$


Notes on Codeforces Problems: Rating 2500

Complexity Analysis for Tree DP: 815C
In this problem, we have a straight-forward DP which has $sz_u \cdot sz_v$ for each children merging. In this case the total running time will be $O(n^2)$ since every pair of vertices will only be merged once.

$O(\sqrt{n})$ possibilities of n / i: 830B
We can express the sum of cut-off as $$\sum_{i} ( d \lceil \frac{a_i}{d}\rceil ) – \text{sum of } a_i$$ $$= d \sum_{i} (\lceil \frac{a_i}{d}\rceil ) – \text{sum of } a_i$$.
The sigma term will only change only $O(n \cdot \sqrt{a_i})$ many times and for each of them, we try to maximize $d$ within the range.

Cycle Under Modulo/ Fermat’s Little Theorem: 311D
It turns out that the length of cycle for a number cubed is always a divisor of 48. This can be explained by the fact that $3^{48} = 1 \bmod ( 95542721 – 1 )$. Therefore, by Fermat’s Little Theorem, we have $a^{3^k} = a^{3^{(k \bmod 48)}} \bmod 95542721$.

Binomial Coefficient/ Pascal’s Triangle: 407C
Don’t forget we have binomial coefficients in Pascal’s triangle! This is the way that we can update those coefficients offline in an array efficiently.

Centroid: 708C
Observation: Find any centroid $v$. We will only cut the edges adjacent to $v$. Otherwise, it will either be not possible (too large) or not optimal (can do better).

Meet-in-the-Middle: 327E, 1257F
When the constraints are really small, always try bit-mask DP or meet-in-the-middle.

MST/ Edge Groups of Kruskal’s Algorithm: 160D, 891C
The process of Krusal’s algorithm can be interpreted as grouping the edges with the same weights and processing them in increasing order of weights. Then for each weight, we want to find a spanning forest. This idea can be used to find the edges that can be/cannot be/might be in the MST.

Dealing with Double Divisions: 138C
If we are frequently doing double multiplicaitons and divisions during sliding window, the error might explode. Instead, either we can take logarithm beforehand and do additions/subtractions instead, or we can use a segment tree to avoid divisions.

Bipartite Graphs over points on 2D plane: 870E, 547D
When we are dealing with configurations of points on 2D plane, we can consider building a bipartite graph where the left (right) part are all possible x (y) coordinates and the points are edges that connects their x and y values.
By doing this construction, 870E becomes directing edges so that $|deg_{in} – deg_{out}| \leq 1$ for each node, and 547D becomes directing edges so that $deg_{in} \geq 1$ for each node.

Doing DFS to enumerate paths in the tree: 490F
We can start DFS from each node and do exactly like the original LIS problem by keeping a DP array. The time for update in each node is $O(1)$ so we can easily roll back when we exit a node.

“Construct optimal answer from any”: 460D
The main difficulty of the problem comes from whether we can choose three integers than have xor sum 0. We can start by any solution and try to tweak it. Then we can see if there are such solution exists, there must be some solution of form “$11000000…, 10111111…, 1111111…$”.

Maximum Pseudoforest/ Greedy: 875F
One can show that this problem is equivelant to finding the maximum weight pseudoforest. Since it is a matroid, we can use greedy to solve it using a way similar to Kruskal’s Algorithm.

Combinatorics / DP: 886E
To solve this problem, we try to use DP and see how to reduce to a smaller problem. Consider $f(n)$ as the number of permutations of $1$ to $n$ that exit early. Then we can consider the position of the largest value: if the largest value is in a early position $i <= n – k – 1$, the algorithm will alway exit early; otherwise the problem will become a smaller one.

Combinatorics: 348D
Let $f(x, y)$ be the number of paths from $x$ to $y$. We can shown the answer is $f((1, 0), (n, m-1)) \cdot f((0, 1), (n – 1, m)) – f((0, 1), (n, m-1)) \cdot f((1, 0), (n – 1, m)) $. The subtracted term is equal to the number of intersecting pairs by consider exchanging the membership of the path at the first time they intersect. The more general form of this problem is discussed here: Lindström–Gessel–Viennot lemma.

Segment Tree: 687D
One can notice that for any certain range of the edges, there will be at most $O(n)$ edges that matters (edges for a spanning tree and an violating edge). Therefore, we can store those edges for each interval in the segment tree, and for each query, we only have $O(n \log n)$ edges to consider.

Maximum Matching: 1198E
First consider covering the grid with unit strip (i.e. $1 \times n$ or $n \times 1$). Then we can reduce the problem into minimum vertex cover, which can be solved by max flow. The number of vertices is large but we can compress the identical ones.

HLD? / Brute Force: 442D
First of all, the answer will be at most $O(\log n)$ because an upper bound is HLD. Then first each newly added vertex, we can just iterative update its parent, and stop when nothing is updated. The amortized complexity is $O(n \log n)$ because each node will be updated at most $O(\log n)$ times.

Subset Sum / Bitset: 356D
While the problem itself is NP-hard, we can use bitset to squeeze the DP solution. To recover the solution, we can record the first item that make sum $j$ available, which can also be done by using bitset.

Constructive Algorithm: 1225F
Sometimes, when dealing with such problems like “finding the maximum answer”, it will be helpful to try to find a upper bound for the answer and show it is always achievable.

Greedy/ We-dont-care-about-everything DP: 822E
While doing brute force transition is too slow, we can just match as long as possible (i.e. longest common prefix) if we do match in a transition. Then the solution will work in $O(n \cdot k)$ after preprocessing LCP and RMQ array.

Cycle under Modulo / Constructive Algorithm: 763C
Consider a (cyclic) sequence where the next number of each number is $(x + d) \text{ mod } m$, where $x$ is the current number and $d, m$ is fixed. Then the answer we want is exactly a segment on this cyclic sequence. Then if $n \leq \frac{m}{2}$, we can see the difference $d$ of a two arbitrary numbers will appear $n – cnt$ times, where $cnt$ is the number of numbers between those two. If $n > \frac{m}{2}$, we can the complement and do the same thing.

Dilworth’s Theorem: 1257G, SPOJ MDOLLS
Dilworth’s Theorem states that the longest anti-chain in a DAG (i.e. the DAG version of “max independent set”) is equal to the size of the smallest path cover. In 1257G, we can prove that the latter is the size of the largest group of divisors that have the same number of prime factors.

Data Structure Keeping the sum of DP Values: 1129D
We try to do fast queries (of sum of values at positions of values of at most $k$) and update (for adding $+1$ or $-1$ to a interval) in a data structure that stores the DP values.
To do this we can do square root decompostion, where in each block we store the count of a each number and a offset to support fast update. This will cost $O(n \sqrt{n})$ for space (which is a little tight) and time.
To save more space, we can observe that the absolute difference in each block can be at most $\sqrt{n}$. Therefore, we can just store a prefix sum of a certain range of values, which reduces the space complexity to $O(n)$.