Sol
神秘题目。
定义 \(pre_i=pre_{i-1}+a_i,suf_i=suf_{i+1}+a_{i+1}\)。
显然一个方案如果合法,\((i,i+1),(j,j+1)\) 位置均没有备选且满足 \(pre_i=suf_j\),那么加上 \((i,i+1),(j,j+1)\) 也同样合法。
所以考虑极长的段 \([l,ll]\) 和 \([rr,r]\) 满足 \(pre_l=pre_{l+1}=\dots=pre_{ll}=suf_{rr}=suf_{rr+1}=\dots=suf_r\),那么枚举选的数的个数 \(p\),此时方案数就是 \(\binom{ll-l+1}{p}\binom{r-rr+1}{p}\)。
注意如果 \([l,ll]=[rr,r]\),那么此时方案数是 \(2^{ll-l+1}\)。
Code
Link。