How to calculate the number of n-tuples of positive integers, satisfying the property that for each adjacent elements in the tuple, the product of elements $A[i] \cdot A[i+1] \leq k$ where $1 \leq i \leq n$. For example, if $n = 2$ and $k = 2$, the answer is $3$ as $2$-tuples are $(1,1), (1,2), (2,1)$.
My Approach:
I am trying to approach this problem with Inclusion-Exclusion principle. First, I will calculate all $n$-tuples with each element in the range $[1,k]$. This is $k^n$. Now I will consider all pairs $(a, b)$ where $1 \leq a \leq k$ and $1 \leq b \leq k$ and $a \cdot b > k$. Those pairs can be calculated easily. Now I will exclude those cases where at least one such pair occurs, then add cases where at least two such pairs occur and so on. But I am not sure how to do this.
Best Answer
Consider the equivalence relation on $\{1,\dots, k\}$ given by $a\sim b$ if $\lfloor k/a \rfloor = \lfloor k/b \rfloor$.
Build the vector of pairs of ints that tells us for each equivalence class how many elements are in that class and what the value of $k/a$ is for its elements.
This can be done in time $\sqrt{k}$ with the hyperbola trick.
After we have built this vector we do a dp table with this vector.
In other words, for each length $l$ we find how many sequences end with an element in that particular equivalence class, of course we need to build prefix sum table for the previous column each time we want to get a new column.
Complexity is $\mathcal O (n \sqrt k)$ so should run fine.