Sorry for the semi-click bait title. Today I spent solving this problem 2189D2 - Little String (Hard Version), the summary of the problem (after simplifications) as follows:

There is a reference strnig $$$w$$$ of length $$$n$$$ consisting of $$$0, 1, ?$$$. Consider a set of possible products

The task is to find the minimum $$$x \in S$$$ such that $$$c \not\mid x$$$.

My solution is slightly diviates from the tutorial. The solution sketch is: the condition $$$c \not\mid x$$$ is equivalent $$$\text{gcd}(x, c) \mod c \neq 0$$$, or in other words $$$\gcd(x, c)$$$ is a proper divisor of $$$c$$$.

Therefore the idea is to have a dynamic programming with the state space consisting of $$$(i, d)$$$, where i is a prefix of the string, and $$$d \mid c$$$. The dp computes the optimal answer $$$x$$$ which

• corresponds to the prefix w[:i]

• $$$\gcd(x, c) = d$$$

The number of dp states is the number of divisors $$$d(c)$$$ times $$$n$$$ which seems fit the constraints.

The dp transition is as follow: suppose we encountered $$$w_i = ?$$$, then we iterate over $$$d \mid c$$$, multiplying the stored optimum $$$x$$$ with either $$$2$$$ or $$$i$$$ and update the dp states $$$(\gcd(x \cdot 2, c) \bmod c, i + 1)$$$ and $$$(\gcd(x \cdot i, c) \bmod c, i + 1)$$$

The problem start here: in order to keep each dp state $$$O(1)$$$ we cannot store the optimum $$$x$$$ for each state explicitley, and the original problem asked to produce the answer modulo some $$$\text{MOD}$$$. However, we cannot store $$$x \bmod \text{MOD}$$$ as well, as for the dp transition we need to have the < comparison between the numbers.

Therefore my approach was to represent each number $$$x$$$ as a triplet:

• $$$\gcd(x, c) \bmod c$$$

• $$$x \bmod \text{MOD}$$$

• $$$\log(x)$$$

After many skill issues I got an AC 364853210 (sorry I didn't clean the solution, it contains the maspy's template codes for fast IO and number theory, my code is at the bottom).

But I believe this can be hacked. The problem that the property $$$\log(a) \cdot \log(b) = \log(a \cdot b)$$$ holds only approximately, so to hack the solution I would need to find two sets of numbers: $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, \dots, b_n$$$ such that

• $$$\prod a_i \lt \prod b_i$$$

• $$$\sum(\log^{\text{c++}}a_i) \gt \sum(\log^{\text{c++}}b_i)$$$, where $$$\log^{\text{c++}}(\cdot)$$$ is the C++ implementation of logarithm.

• the program is forced at some execution path to compare these two.

The preliminary estimate, that worst case I store up untill $$$\log(n!) \sim n \log n $$$, therefore the doubles worst case are in the $$$10^5$$$ range. I am not sure, is it sufficient to lose precision sufficiently to have the comparison wrong.

If the answer is yes, then I would be happy to know if it's possible store the values as 2 or 3 doubles. For the case of regular integer numbers, it's well establised to use bigint, so I'm wondering is there are "big doubles". And how the operations over these "big doubles" should be implemented. Thank you!