设 A/B/C/D 为 $0/1/2/3$，将 $s_i$ 变成 $(s_i-i)\bmod 4$，操作变成选择相邻四个相同数，让他们同时变为某个数.

按如下方式定义 $P(s)$：

• 维护序列 $t$，初始 $t$ 为空，按 $i=1,2,\cdots,n$ 依次将 $s_i$ 加入 $t$ 末尾，若加入后 $t$ 末尾四个数相同，则将末尾四个数都删掉. 最终 $t$ 就是 $P(s)$.

不难发现，如果 $s_1$ 可以通过一次操作变成 $s_2$，则 $P(s_1)=P(s_2)$.

因此问题变为，问有多少 $s’$ 满足 $P(s)=P(s')$.

设 $f_i$ 为，假设往 $t$ 中加入了 $4i$ 个数，且第一个数为 $0$，且加入过程中序列一直不为空，满足条件的方案数.

考虑转移.

考虑最后一次操作，显然是将序列的 $4$ 个 $0$ 同时弹出.

设这 $4$ 个 $0$ 加入的时刻为 $1=p_1 < p_2 < p_3 < p_4=4i$.

若 $p_{x} < y < p_{x+1}$，那么在加入第 $y$ 个数前，若序列只包含 $x$ 个 $0$，则加入的第 $y$ 个数必然不能为 $0$，否则序列会提前消空.

因此设 $F(x)=\sum_{i\geq 0}f_ix^i$，则有转移 $F=x(\dfrac1{1-3F})^3$.

考虑如何计算答案，同样考虑维护 $t$ 的过程，设最终 $t$ 剩下的数加入时间为 $q_{1\sim k}$，那么 $q$ 会把时间划分为若干段，第一段是 $\dfrac1{1-4F}$，其余每一段都是 $\dfrac1{1-3F}$，因此答案为 $[x^n]\dfrac1{1-4F}(\dfrac1{1-3F})^k$.

设 $H=\dfrac1{1-4x}(\dfrac1{1-3x})^k$，则答案为 $[x^n]H(F)$.

设 $F$ 的复合逆为 $G$，则 $x(1-3x)^3=G$，使用扩展另类拉反： $$ \begin{aligned} [x^n]H(F)&=[x^n]HG'(\frac xG)^{n+1}\\ &=[x^n]\dfrac1{1-4x}(\dfrac1{1-3x})^k((1-3x)^3-9x(1-3x)^2)\frac1{(1-3x)^{3(n+1)}}\\ &=[x^n]\dfrac{1-12x}{1-4x}\cdot\dfrac1{(1-3x)^{k+3n+1}}\\ \end{aligned} $$ 复杂度 $O(n)$.