Original proposer: ynymxiaolongbao

Let \(C_i\) be the set of color with which cells \(i-1\) and \(i\) can be both painted.

Define \(\mathrm{dp}[i][c]\) as the number of ways to paint cells so that the rightmost painted cell is cell \(i\) and it is colored with color \(c\). (DP stands for Dynamic Programming.) By definition:

\(\mathrm{dp}[i][c]=\begin{cases} S_{i-2}-\mathrm{dp}[i-2][c] & c\in C_i\\ 0 & c\not \in C_i, \end{cases}\)

so we obtain the recurrence relations

\(S_k\\ =S_{k-1}+\sum_c \mathrm{dp}[k][c]\\ =S_{k-1}+|C_k|S_{k-2}-\sum_{c\in C_k}\mathrm{dp}[k-2][c].\)

We will consider how to compute the third term fast.

Define an array \(T_k\) whose elements are integers or \(\bot\) by:

\(T_k[c]=\begin{cases} \mathrm{dp}[k-2][c] & c \in C_k\\ \bot & c \not \in C_k. \end{cases}\)

Also define \(|T_k|=|\{c \mid T_k[c]\neq \bot\}|\) and \(\mathop{\mathrm{sum}}T_k=\sum_{T_k[c]\neq \bot}T_k[c]\).

By definition of \(\mathrm{dp}\), the transition from \(T_{k-2}[c]\) to \(T_{k}[c]\) is:

• \(T_{k-2}[c] \to S_{k-4}-T_{k-2}[c]\) if \( c \in C_k \cap C_{k-2}\),
• \(\bot \to 0\) if \(c \in C_k \setminus C_{k-2}\),
• \(T_{k-2}[c] \to \bot\) if \(c \in C_{k-2} \setminus C_k\),
• \(\bot \to \bot\) otherwise.

Therefore, if we define \(T'_k[c]=S_{k-4}-T_{k-2}[c]\), there are at most \(2M\) pairs \((k,c)\) such that \(T'_k[c]\neq T_k[c]\). The transformation from \(T_{k-2}\) to \(T'_k\) can be done by managing the global \(-1\) factor and constant offset, \(|T_k|\) and \(\mathop{\mathrm{sum}}T_k\), so the update can be performed in-place in \(O(1)\) time. Meanwhile, the difference between \(T'_k\) and \(T_k\) can be handled naively. In total, \(T_k\) can be found sequentially in a total of \(O(N+M)\) time. Using

\(S_k=S_{k-1}+|T_k|S_{k-2}-\mathop{\mathrm{sum}}T_k,\)

the problem can be solved in a total of \(O(N+M)\) time.