I will try to explain the main ideas in my solution for this problem. Actually, my solution is quite similar to the general idea described in the editorial - the major difference consists of the way I compute **F2(X)** = the product of all the odd numbers <= X.
Let's consider the binary representation of **X** and let's traverse its bits from the most significant one to the least significant one. Thus, let's assume that **X = 2^p(1) + 2^p(2) + ... + 2^p(q)** (where **p(1) > p(2) > ... > p(q)**).
The first bit is handled in a special manner. We want to compute the product of all the odd numbers **1 * 3 * ... * (2^p(1) - 1)**. Actually, this value will be precomputed and I will denote it by **SPODD(p(1),0)** (I will explain later what **SPODD(i,j)** means).
Let's assume now that we reached the bit **p(r >= 2)** and let's denote by **Y = 2^p(1) + 2^p(2) + ... + 2^p(r-1)** (i.e. the sum of all the bits of X which are more significant than p(r)). We now want to compute the product of all the odd numbers in the range **(Y + 1) ... (Y + 2^p(r))**. If **p(r)** is **1** or **0** then the product consists of just one number: **(Y+1)**.
Otherwise (if **p(r) >= 2**) then the product will be **(Y + 1) * (Y + 3) * ... * (Y + 2^p(r) - 1)** (there are **2^(p(r)-1)** odd numbers in the product). This product can be expressed as:
- **Y^0** * (the product of all the odd numbers **1 * 3 * ... * (2^p(r) - 1))** +
- **Y^1** * (the sum of all the products **u(1) * ... * u(2^(p(r) - 1) - 1)**, where **{u(1), ..., u(2^(p(r) - 1) - 1)}** goes over all the subsets of the odd numbers **{1,3,...,2^p(r) - 1}** having **2^(p(r) - 1) - 1** elements) +
- ... +
- **Y^j** * (the sum of all the products **u(1) * ... * u(2^(p(r) - 1) - j)**, where **{u(1), ..., u(2^(p(r) - 1) - j}** goes over all the subsets of the odd numbers **{1, 3, ..., 2^p(r) - 1}** having **2^(p(r) - 1) - j** elements) +
- ... (the sum contains **2^(p(r) - 1) + 1** terms overall).
Now I can introduce the values **SPODD(i,j)** = the sum of all the products **u(1) * ... * u(2^(i - 1) - j)**, where **{u(1), ..., u(2^(i - 1) - j}** goes over all the subsets of the odd numbers **{1, 3, ..., 2^i - 1}** having **2^(i - 1) - j** elements. Thus, **SPODD(i,j)** means that we consider all the subsets of odd numbers < 2^i having **2^(i-1) - j** elements. Obviously, by the definition, **SPODD(i,0) = 1 * 3 * ... * ~~(2^(i-1) ~~(2^i - 1)**.
Our sum of terms mentioned earlier (Y^0 * ... + Y^1 * ... + ...) can be expressed now as **Y^0 * SPODD(p(r), 0) + Y^1 * SPODD(p(r), 1) + ... + Y^j * SPODD(p(r), j) + ...**
Let's notice now that we only ever need at most **120** terms from this sum, when computing it modulo **2^120**. Note that **Y** is an even number. Thus, only the terms corresponding to **Y^0, Y^1, ..., Y^119** may have a non-zero remainder when divided by **2^120** (all the other terms are **0** modulo **2^120**). Actually, we can do even better. When we reached the bit **p(r)** (**r>=2**), **Y** is an even number which is a multiple of at least **2^(p(r) + 1)** (because **Y=2^p(1) + ... + 2^p(r-1)** and **p(r-1) > p(r)**). Thus, only the terms corresponding to **Y^0, Y^1, ..., Y^k** may be non-zero (mod **2^120**), where **k = 119 / p(r-1)**.
When we add things up, we notice that, in the worst case, we will need around **119/119 + ... + 119/3 = O(n * log(n))** 120-bit operations (**n = 120**) for computing **F2(X)** (I stopped at 119/3 because we only use this method for p(r)>=2 and, thus, p(r)+1>=3 ; for p(r)=1 or 0 I explained earlier that the result is easy to compute).
Since we evaluate **O(n)** different **F2(X)** values per test case, this adds up to an **O(n^2 * log(n))** time complexity per test case.
For now I left out a very important part - how to precompute all the numbers **SPODD(i,j)** (**i,j <= 120**) in **O(120^3)** time. I will explain this at another time, as the explanation is more complicated than anything I wrote here.