Shohag Loves Counting (Easy Version)
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2800
Tags: combinatorics, dp, math, number theory

This is the easy version of the problem. The only differences between the two versions of this problem are the constraints on $$$t$$$, $$$m$$$, and the sum of $$$m$$$. You can only make hacks if both versions of the problem are solved.

For an integer array $$$a$$$ of length $$$n$$$, define $$$f(k)$$$ as the greatest common divisor (GCD) of the maximum values of all subarrays$$$^{\text{∗}}$$$ of length $$$k$$$. For example, if the array is $$$[2, 1, 4, 6, 2]$$$, then $$$f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4]), \operatorname{max}([1, 4, 6]), \operatorname{max}([4, 6, 2])) = \operatorname{gcd}(4, 6, 6) = 2$$$.

An array is good if $$$f(i) \neq f(j)$$$ is satisfied over all pairs $$$1 \le i \lt j \le n$$$.

Shohag has an integer $$$m$$$. Help him count the number, modulo $$$998\,244\,353$$$, of non-empty good arrays of arbitrary length such that each element of the array is an integer from $$$1$$$ to $$$m$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains an integer $$$m$$$ ($$$1 \le m \le 10^5$$$).

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, output an integer — the number of valid arrays modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the valid arrays are $$$[1]$$$, $$$[1, 2]$$$, $$$[2]$$$, and $$$[2, 1]$$$.

In the second test case, there are a total of $$$29$$$ valid arrays. In particular, the array $$$[2, 1, 4]$$$ with length $$$n = 3$$$ is valid because all elements are from $$$1$$$ to $$$m = 5$$$ and $$$f(1)$$$, $$$f(2)$$$ and $$$f(n = 3)$$$ all are distinct:

- $$$f(1) = \operatorname{gcd}(\operatorname{max}([2]), \operatorname{max}([1]), \operatorname{max}([4])) = \operatorname{gcd}(2, 1, 4) = 1.$$$
- $$$f(2) = \operatorname{gcd}(\operatorname{max}([2, 1]), \operatorname{max}([1, 4])) = \operatorname{gcd}(2, 4) = 2.$$$
- $$$f(3) = \operatorname{gcd}(\operatorname{max}([2, 1, 4])) = \operatorname{gcd}(4) = 4.$$$

Example input:
3
2
5
9

Example output:
4
29
165

Editorial:
Let $$$s_k$$$ be the sequence of $$$k$$$ length subarray maximums of the array. Then $$$s_{k + 1}$$$ is just the adjacent maximum sequence of $$$s_k$$$.
Also, let $$$g_k$$$ be the GCD of the elements of $$$s_k$$$. Then notice that every element of $$$s_{k + 1}$$$ is also divisible by $$$g_k$$$. That is $$$g_k$$$ divides $$$g_{k + 1}$$$.
For the array to be good, $$$g_k$$$ must be different for all $$$k$$$. So $$$g_k < g_{k + 1}$$$ and $$$g_k$$$ divides $$$g_{k + 1}$$$. This means if the length of the array is $$$n$$$, then $$$n \le \lfloor \log_2 m \rfloor + 1$$$.
Now consider a non-decreasing sequence of integers $$$a$$$ of length $$$n$$$ such that $$$1 \le a_i \le m$$$ for all $$$i$$$. Then the $$$k$$$ length subarray maximums of $$$a$$$ are just the last $$$k$$$ elements of $$$a$$$. So $$$g_k$$$ is the GCD of the last $$$k$$$ elements of $$$a$$$. Then for $$$g_k$$$ to be different for all $$$k$$$, all the elements of $$$a$$$ must be distinct. So the condition for $$$a$$$ to be good is that the elements are distinct and all suffix GCDs are distinct as well.
Next the question is how many permutations of this increasing sequence $$$a$$$ is good as well? To count this, lets start from $$$s_n$$$. $$$s_n$$$ is just $$$[a_n]$$$. Now consider $$$s_{n - 1}$$$. We need to put $$$a_{n - 1}$$$ in the sequence such that the adjacent maximum sequence of $$$s_{n-1}$$$ becomes $$$s_n$$$. For this we clearly have $$$2$$$ ways: $$$[a_{n - 1}, a_n]$$$ and $$$[a_n, a_{n - 1}]$$$.
Now consider $$$s_{n - 2}$$$. We need to put $$$a_{n - 2}$$$ in the sequence such that the adjacent maximum sequence of $$$s_{n-2}$$$ becomes $$$s_{n-1}$$$. For this we again have $$$2$$$ ways because $$$a_{n - 2}$$$ can be inserted in $$$2$$$ places: before $$$a_{n - 1}$$$ or after $$$a_{n - 1}$$$.
Similarly for all other $$$s_k$$$ we have $$$2$$$ ways to insert it: putting it before $$$a_{k + 1}$$$ or after $$$a_{k + 1}$$$. So the total number of good permutations of $$$a$$$ is $$$2^{n - 1}$$$.
So our problem reduces to the following:
• Select a length $$$n$$$ such that $$$1 \le n \le \lfloor \log_2 m \rfloor + 1$$$.
• Count the number of strictly increasing sequences of length $$$n$$$ such that all suffix GCDs are distinct.
• Multiply the answer by $$$2^{n - 1}$$$.
• Sum up the answer for all valid $$$n$$$.
For a fixed $$$n$$$, let's count the number of strictly increasing sequences of length $$$n$$$ such that all suffix GCDs are distinct.
Let $$$\text{dp}_{i, g}$$$ be the number of strictly increasing sequences of length $$$n$$$ such that the starting element is $$$i$$$ and the GCD of the elements is $$$g$$$.
Now iterate from $$$i = m$$$ to $$$1$$$. Then the transition is to iterate over the next suffix GCD $$$h$$$ such that $$$g$$$ divides $$$h$$$, $$$g < h \le m$$$ and $$$g = \text{gcd}(i, h)$$$ and then add $$$\text{dp}_{*, h}$$$ to $$$\text{dp}_{i, g}$$$. Here $$$\text{dp}_{*, h}$$$ is the sum of all $$$\text{dp}_{j, h}$$$ for all $$$j > i$$$.
Another way to look at the transition is that for a fixed $$$i$$$, we iterate over all $$$h$$$ and if $$$\text{gcd}(i, h) < h$$$, then we add $$$\text{dp}_{*, h}$$$ to $$$\text{dp}_{i, \text{gcd}(i, h)}$$$.
But doing everything like this would still be $$$O(m^2 \log m)$$$ which is too slow.
Notice that all $$$g$$$ are the divisors of $$$i$$$. Here the main difficulty is that we need update at the index $$$\text{gcd}(i, h)$$$ over all $$$h$$$ but it is hard to track the exact gcd but what's easier is to track the multiple of the gcd.
So for each $$$g$$$, let's say we know the sum of all $$$\text{dp}_{*, h}$$$ over all $$$h$$$ such that $$$g$$$ divides $$$h$$$. So this sums up all $$$\text{dp}_{*, h}$$$ such that $$$g$$$ divides $$$\text{gcd}(i, h)$$$.
Then using inclusion exclusion on the divisors of $$$i$$$ we can get the sum of all $$$\text{dp}_{*, h}$$$ for all $$$h$$$ such that $$$g$$$ is exactly $$$\text{gcd}(i, h)$$$. This will take $$$O(\sigma(i)^2)$$$ time for each $$$i$$$ where $$$\sigma(i)$$$ is the number of divisors of $$$i$$$.
And once we calculate the $$$\text{dp}_{i, g}$$$ for some $$$i$$$ and $$$g$$$, then before transitioning to $$$i - 1$$$, we can add the value of $$$\text{dp}_{i, g}$$$ to all divisors of $$$g$$$ to get the value of $$$\text{dp}_{*, h}$$$ faster in the future. To keep track of this, we can use a separate array.
So for a fixed $$$n$$$, the time complexity is $$$O(\sum_{i = 1}^{m} \sigma(i)^2)$$$. And we need to do this for all $$$n$$$ from $$$1$$$ to $$$\lfloor \log_2 m \rfloor + 1$$$.
So the overall time complexity is $$$O(\log m \cdot \sum_{i = 1}^{m} \sigma(i)^2)$$$. We actually allowed this to pass in F1.
We can make the time complexity much better with a simple modification in the dp. Note that we don't need to use the length of array in the dp state. As we need to sum up after multiplying by $$$2^{\text{length of array} - 1}$$$ at the end, we can modify the dp to directly store the sum of $$$2^{\text{length of array} - 1}$$$. So we can just multiply the dp by $$$2$$$ during each transition.
So the time complexity becomes $$$O(\sum_{i = 1}^{m} \sigma(i)^2)$$$. This is very fast for F1.