Antifibonacci Cut

Observation 1: the plain DP is easy, the memory limit is the real bastard

Let $S$ be the current concatenated string, and let $dp[i]$ be the number of valid ways to cut the first $i$ characters of $S$.

Of course, $dp[0]=1.$ For $i\ge 1$, choose the start of the last piece at position $j+1$. Then $dp[i]=\sum_{j=0}^{i-1} dp[j]-\sum_{j:\ S_{j+1..i}\text{ is a Fibonacci string}} dp[j].$

If we define $pref[i]=\sum_{t=0}^{i} dp[t],$ then this becomes $dp[i]=pref[i-1]-bad[i],$ where $bad[i]$ is the total weight of cuts whose last piece is forbidden.

So far, so standard.

If the memory limit were sane, we'd just store all $dp[i]$ and test all Fibonacci lengths. But with 4 MB, storing an array of size $3\cdot 10^6$ is dead on arrival. So we need to remember only the old $dp$ values that can still matter later.

Observation 2: all long forbidden strings lie on one infinite word

For $k\ge 1$, the Fibonacci strings are $f_1=\texttt{1},\quad f_2=\texttt{10},\quad f_3=\texttt{101},\dots$ and every $f_k$ is a prefix of the infinite Fibonacci word $F=101101011011010110\dots$ (the limit of the recursion $f_i=f_{i-1}+f_{i-2}$).

The only forbidden string not on this chain is $f_0=\texttt{0}.$ That one is a length-$1$ nuisance; we'll special-case it.

Now fix a cut position $j$. As we scan the text further right, the substring starting at $j+1$ can only become some $f_k$ if it keeps matching a prefix of $F$ at every intermediate length.

Once it mismatches, it's over. That cut position is useless forever.

This is the key reason we do not need the whole $dp$ array.

Observation 3: keep only alive cut positions

After processing some prefix of length $pos$, call a cut position $j$ alive if the suffix $S[j+1..pos]$ is equal to a prefix of $F$.

If its length is $\ell=pos-j$, then the only data we need from that cut is exactly $dp[j]=dp[pos-\ell].$ So we store alive states as pairs $(\ell, w), \qquad w=dp[pos-\ell].$

There is at most one alive state for each length $\ell$, because the starting position is then fixed.

Also, all alive lengths are suffixes of the current string which are prefixes of $F$. Equivalently, they are exactly the border chain of the longest matched prefix of $F$.

Observation 4: the transition is tiny

Suppose we already processed $pos$ characters, and we read a new character $c$.

How do alive states change?

• A fresh cut before this character creates a length-$1$ piece.

  • If $c=\texttt{1}$, it matches the prefix of $F$ of length $1$, so we get a new alive state $(1, dp[pos]).$
  • If $c=\texttt{0}$, it matches only $f_0$, which is forbidden immediately but can never grow into a longer Fibonacci string, so we do not keep it alive.

• Any old alive state $(\ell,w)$ survives iff the next character of $F$ matches: $F[\ell+1]=c.$ Then it becomes $(\ell+1, w).$

That's it. No hidden nonsense.

So after reading one character, we can build the new alive list by just scanning the old one.

Observation 5: how to compute bad

After constructing the alive states for the new position, which of them correspond to forbidden last pieces?

Exactly those whose length is a Fibonacci-string length for $k\ge 1$: $1,2,3,5,8,13,\dots$ Because all those lengths correspond to prefixes $f_k$ of $F$.

And we must also add the special case $f_0=\texttt{0}$, i.e. the fresh length-$1$ piece when the current character is $\texttt{0}$.

So if the new position is $i$,

+ \sum_{(\ell,w)\in alive_i\atop \ell\in\{1,2,3,5,8,\dots\}} w.$$ Then simply $$dp[i]=pref[i-1]-bad[i] \pmod{998244353}.$$ ## Why is the alive list small? This is the one combinatorics lemma you need to swallow. A classical fact about the Fibonacci word is: > Every prefix of $F$ has a failure/border chain of length $O(\log N)$. One way to phrase it: prefixes of the Fibonacci word are standard / semi-standard Fibonacci words, their shortest periods are Fibonacci lengths, and when you jump to the longest proper border, that shortest period strictly decreases. Since there are only $O(\log N)$ Fibonacci lengths up to $N$, the whole chain is logarithmic. Our alive lengths are exactly such a border chain. Therefore the number of alive states is always $$O(\log N).$$ So each character is processed in $O(\log N)$ time. ## Precomputing the infinite Fibonacci word We need fast access to $F[t]$ for $t\le 3\cdot 10^6$. Just build the first $3\cdot 10^6+1$ characters of $F$ once. That's only about **3 MB**, which fits the stupidly tiny memory limit. The clean way is recursive generation from the definition of Fibonacci strings: - $f_0=\texttt{0}$, - $f_1=\texttt{1}$, - $f_k=f_{k-1}+f_{k-2}$. Pick some large $k$ with $|f_k|\ge 3\cdot 10^6+1$, and recursively output only the needed prefix. ## Correctness sketch We maintain the invariant: > After processing $pos$ characters, the stored alive list consists exactly of all lengths $\ell$ such that the suffix of length $\ell$ equals $F[1..\ell]$, and its stored weight is $dp[pos-\ell]$. This is true initially (empty list). When we append one character $c$: - any new alive suffix of length $1$ is possible iff $c=\texttt{1}$, with weight $dp[pos]$; - any new alive suffix of length $\ell+1$ must come from a previous alive suffix of length $\ell$, and it survives iff the next needed Fibonacci-word character equals $c$. So the transition builds exactly the new alive list. Then `bad` counts exactly those cuts whose last piece is one of the forbidden Fibonacci strings: - $\texttt{0}$ is handled separately, - all other forbidden strings are precisely the alive states whose lengths are Fibonacci lengths $1,2,3,5,\dots$. Therefore the recurrence computes the exact number of valid cuts. ## Complexity Let $$M=\sum_{i=1}^{n} |s_i|.$$ - Precomputing the needed prefix of $F$: $O(M_{\max})$ where $M_{\max}=3\cdot 10^6+1$. - Processing each character: $O(\#alive)=O(\log M)$. So total time is $$O(M\log M).$$ Memory usage is $$O(M_{\max})$$ for the stored prefix of the Fibonacci word, plus a tiny $O(\log M)$ alive list. In actual bytes: about **3 MB** for the word itself, which is exactly the kind of cursed engineering this problem wanted.