Simons and Dividing the Rhythm

Research check: the official Codeforces editorial for 2205E gives the intended DP over borderless segments and KMP-style border detection. I also checked a third-party accepted-code writeup that uses the same prefix-function transition: Znzryb's blog. The statement here is still the source of truth.

We are given the final array $T$. If Simons starts from $S$ and reverses every block of some partition, then reversing the story is easier: choose a partition of $T$, reverse every block, and concatenate them. That gives a candidate $S$.

So if a partition is

$$T = B_1 B_2 \cdots B_k,$$

then the produced starting array is

$$S = \operatorname{rev}(B_1)\operatorname{rev}(B_2)\cdots\operatorname{rev}(B_k).$$

If all elements were distinct, every partition would probably be unique and the answer would be $2^{n-1}$. But duplicates/patterns ruin that. For example, for $T=[1,1]$, both partitions $[1]\,[1]$ and $[1,1]$ produce the same $S=[1,1]$. Counting partitions directly is fake money.

Define a border of an array segment $X$ as a nonempty proper prefix of $X$ that is also a suffix of $X$. A segment is unbordered if it has no border.

The key claim is:

Distinct obtainable arrays $S$ are in one-to-one correspondence with partitions of $T$ into unbordered segments.

First, why every $S$ has such a partition. Suppose some block is bordered. Let the shortest border have length $b$, and write the block as

$$X = A M A,$$

where $A$ is that border. For the shortest border, we can ensure $2b \le |X|$; otherwise the overlap creates an even shorter border. If $2b=|X|$, then $M$ is empty.

Now compare reversing the whole block versus splitting it:

$$\operatorname{rev}(A M A) = \operatorname{rev}(A)\operatorname{rev}(M)\operatorname{rev}(A).$$

That is exactly what we get by reversing $A$, $M$, and $A$ separately. So a bordered block can be replaced by smaller blocks without changing $S$. Repeating this process must terminate, giving an all-unbordered partition.

Second, why this partition is unique. Assume two all-unbordered partitions produce the same $S$. Look at the first position $l$ where their next block length differs. Say one partition takes $T[l..r]$ and the other takes the longer block $T[l..R]$, with $r<R$.

In the produced $S$, the shorter block contributes

$$\operatorname{rev}(T[l..r]).$$

The longer block starts with the reverse of its suffix of the same length, so equality of the produced arrays forces

$$\operatorname{rev}(T[l..r]) = \operatorname{rev}(T[R-(r-l)..R]).$$

Reversing both sides gives

$$T[l..r] = T[R-(r-l)..R].$$

So $T[l..R]$ has a proper border of length $r-l+1$. That contradicts the longer block being unbordered. Therefore two different unbordered partitions cannot produce the same $S$.

Now the DP is straightforward.

Let

$$dp[i] = \text{number of canonical unbordered partitions of } T[1..i].$$

The empty prefix has one partition, so $dp[0]=1$. If the last block is $T[l..r]$ and it is unbordered, then every canonical partition of $T[1..l-1]$ can be extended by this block:

$$dp[r] \mathrel{+}= dp[l-1].$$

So we only need to know whether every segment $T[l..r]$ is unbordered.

For each fixed start $l$, run the prefix-function/KMP computation on the suffix

$$U = T[l], T[l+1], \ldots, T[n].$$

For a prefix $U[1..L]$, the prefix function value $\pi[L]$ is the length of its longest proper border. Therefore

$$T[l..l+L-1] \text{ is unbordered} \iff \pi[L]=0.$$

Then we add $dp[l-1]$ to all valid endpoints.

Implementation uses 0-based indexing:

• dp[0] = 1 means empty prefix.
• For start l, compute prefix function for t[l..n-1].
• If pi[len-1] == 0, then t[l..l+len-1] is unbordered, so dp[l+len] += dp[l].

Edge cases:

• $n=1$: one segment, answer $1$.
• All values equal: only singleton blocks are unbordered, answer $1$.
• All values distinct: every segment is unbordered, answer $2^{n-1}$ modulo $998244353$.
• A segment like $[1,2,3,1]$ is not safe just because it is not a repeated string. It has border $[1]$, so it is redundant. The condition is no border at all, not "not a full repetition". Important distinction; otherwise the solution gets cooked.

For one test case, the sum of suffix lengths processed by KMP is

$$\sum_{l=1}^{n} (n-l+1) = O(n^2).$$

The total $n$ over test cases is at most $8000$, so the total runtime is $O(\sum n^2)$, bounded by $O(8000^2)$, and memory is $O(n)$.