给定一个整数 $n$ 和一个长度为 $m$ 的数组 $a$。对于所有 $k=1,2,\cdots,n$，求有多少个字符串满足：

• 由 $k$ 个 - 和 $k$ 个 + 组成。
• 结尾的 - 数量在 $a$ 中出现。

即求 $\sum_a [a \in \{a_n\}]d_a \binom{2n-1-a}{n-1}$，$d_a$ 是 0/1 变量，表示位置 $a$ 上写的是 + 还是 -，

我们选取一组系数 $e_a$，使得 $\sum_a d_a \binom{2n-1-a}{n-1} = \sum_a e_a \binom{2n}{n+a}$。

我们有 $\binom{2n}{n+a} = \sum_k \binom{2n-k-1}{n-1} \binom{k}{a}$，所以： $$ \sum_a e_a \binom{2n}{n+a} = \sum_a e_a \sum_k \binom{2n-k-1}{n-1} \binom{k}{a} = \sum_k \binom{2n-k-1}{n-1} \sum_a \binom{k}{a} e_a $$

即若 $\forall k$ 都有 $d_k = \sum_{a=0}^k \binom{k}{a} e_a$，那么 $e$ 可取，由此可以构造 $e_k = \sum_{a=0}^k \binom{k}{a} (-1)^{a-k} d_a$。

于是问题等价于对任意 $n$ 求 $\sum_a e_a \binom{2n}{n+a}$，即 $[x^0]\left(x+\frac{1}{x}\right)^{2n} Q(x)$，其中 $Q(x) = \sum e_a x^{-a}$。

然后考虑分治。设当前区间长度为 $L$，在 $Q(x)$ 中只需要保留 $[-L, L]$ 内的幂次。将该区间划分为两半，分别在两个子区间上求解 $Q(x)$ 和 $Q(x)\left(x+\frac{1}{x}\right)^{2(L/2)}$。此时可以做到单层 $O(L \log L)$，总复杂度 $O(L\log^2 L)$。