【A】Bad Apple

AT_arc189_a [ARC189A] Reversi 2

考虑每个连续段都是独立的。先判掉 \(a_1,a_n\) 不合法的情况，和连续段长度是偶数的情况。
对于一个连续段，有 \(f_{i}=\sum_{i=1}^n f_{i-1}\times f_{n-i}\times \binom{n}{i},f_0=1\)。打表发现等于 \(f_{i}=\prod_{j=1}^i (2j-1)\)。