Strange Process

Research checked: the official Codeforces Kotlin Heroes 14 editorial/reference solution for 2199I uses the same $7$-bit mask DP idea, and the status page confirms accepted submissions. The explanation below is rebuilt from the statement, not copied.

The process looks like scary number theory plus $n$ moving objects, but the objects are independent. The only shared thing is the output array $b$: at each stage we either write $0$ or name one element.

For a single element, represent its value by prime exponents. In one stage, one exponent can go up by $1$, go down by $1$ if possible, or everything can stay the same. Therefore the minimum number of stages needed to move from value $x$ to value $y$ is

$$d(x,y)=\sum_p |v_p(x)-v_p(y)|.$$

Equivalently,

$$d(x,y)=\Omega\left(\frac{xy}{\gcd(x,y)^2}\right),$$

because the common prime powers cancel and the remaining prime factors are exactly the exponent changes. If we have at least $d(x,y)$ stages, we do those changes and waste extra stages by staying unchanged. No parity nonsense, thankfully.

So an output array $b$ is achievable exactly when every positive label is individually feasible. If label $k$ appears at stages

$$t_1<t_2<\dots<t_r,$$

then we need

$$d(1,c_{t_1})\le t_1$$

and for every consecutive pair,

$$d(c_{t_j},c_{t_{j+1}})\le t_{j+1}-t_j.$$

This is necessary because the element must physically move between those values. It is sufficient because every element can follow its own checkpoints independently; stages where it is not named impose no extra restriction.

Now the key bound: all values $c_i$ are at most $50$. Precomputing $d(x,y)$ for $1\le x,y\le 50$ gives maximum $8$; for instance, $27=3^3$ and $32=2^5$ are distance $8$. That means a label whose last appearance was at least $8$ stages ago is automatically compatible with the current value. Only labels last seen $1$ through $7$ stages ago need to be remembered. That is the whole trick; otherwise this problem is a swamp.

Let $K=7$. We process stages from left to right with a DP over masks of length $K$.

After processing all stages before current index $i$ (0-indexed), bit $j$ of the mask means:

$$\text{the label last used at stage } i-j-1 \text{ is still tracked}.$$

There can be at most one such label per previous stage, so the mask fully identifies which recent last-use positions are occupied. The actual label IDs are already counted inside the DP value.

For each state mask:

1. Age everything by one stage:

$$shifted=(mask\ll 1)\ \&\ ((1\ll K)-1).$$

2. Write $b_i=0$. Add $dp[mask]$ to ndp[shifted].

3. Choose a label not currently tracked. There are

$$n-\operatorname{popcount}(mask)$$

such labels. This includes labels never used and labels last used at least $8$ stages ago. If it is truly the first use, we need $d(1,c_i)\le i+1$; when old expired labels can exist, this condition is already always true because $d(1,c_i)\le 5$. So the single check $d(1,c_i)\le i+1$ is enough. If it holds, add

$$(n-\operatorname{popcount}(mask))\cdot dp[mask]$$

to ndp[shifted | 1].

4. Reuse a tracked label. If bit $j$ is set, that label was last used $j+1$ stages ago, at previous index

$$prev=i-j-1.$$

It can be reused now iff

$$d(c_{prev},c_i)\le j+1.$$

After reuse, its old aged bit is removed and bit $0$ is set, because its newest use is the current stage.

At the end, every DP state is a complete achievable prefix of length $m$, so the answer is

$$\sum_{mask} dp[mask] \pmod{998244353}.$$

The zero array, $n=1$, and repeated values are handled naturally. Reusing an expired label is counted through the “not currently tracked” transition, which is why the multiplier is $n-\operatorname{popcount}(mask)$ instead of some overcomplicated “never used” bookkeeping. That tempting bookkeeping is bait.

Precomputing distances costs $O(50^2\log 50)$. The DP has $m$ layers, $2^7$ masks, and at most $7$ reuse attempts per mask, so the total complexity is

$$O(m\cdot 2^7\cdot 7),$$

with $O(2^7)$ memory.