题解：CF2135E2 Beyond the Palindrome (Hard Version)

反射容斥入门。

删除 $\1\0$ 的操作容易让我们想到括号匹配，进一步我们可以想到转化为折线，定义 $\1$ 为 $+1$，$\0$ 为 $-1$。

从左往右走，结果中 $\0$ 的数量为折线的最低点（与起点高度差）。

从右往左走，结果中 $\0$ 的数量为折线最高点与终点的高度差。

由于 $\0\1$ 数量差一定，所以一个串合法当且仅当 $l+r=s_n$，其中 $l$ 为最低点高度，$r$ 为最高点高度，$s_n$ 为终点高度。

答案可以表示为

其中 $g(l,r,m)$ 表示从 $(0,0)$ 走到 $(n,m)$，最低点恰好为 $l$，最高点恰好为 $r$ 的方案数。

这两个恰好不好处理，容斥。

其中 $f(l,r,m)$ 表示不碰到 $y=l$ 和 $y=r$ 两条直线的方案数。

根据反射容斥的知识，我们每碰到一条直线，就把这之前的部分翻转，翻转前的方案和翻转后的一一对应。

考虑翻转对起点的影响。

$L$ 表示应用对 $y=l$ 翻转，$R$ 同理。

设 $ways((x,y))$ 表示从 $(x,y)$ 走到终点 $(n,m)$ 的方案数，这题中 $x$ 一定为 $0$，后面直接省略，简单的推导我们可以得到 $ways((x,y))=\binom{n}{\frac{n+m-y}2}$。

$I$ 表示初始的起点，即 $(0,0)$。（这些东西都可以写成矩阵的形式，但这样讲应该也挺容易理解的。）

即你现在有一个无限长的纸条写着 $\dots LRLRLR\;I\;LRLRLR\dots$，正着走即为第一步走 $L$，倒着走即为第一步走 $R$。

走了偶数距离：系数为 $1$，走到 $2k$ 时方案为 $\D\binom{n}{\frac{n+m}2-k(r-l)}$。

走了奇数距离：系数为 $-1$，走到 $2k-1$ 时（相当于先走到 $2k$，最后再走一步 $R$）方案为 $\D\binom{n}{\frac{n+m}2-(r-k(r-l))}$。

由于 $k$ 可取所有整数，为了让式子好看一点，做一点变换。

但是做到这里还是没法通过 E1。

注意 $m=l+r+t=t-(r-l)+2r,t\in\{-1,0,1\}$，定义 $k'=k-\frac12$。

枚举 $d=r-l$，把 $d$ 相同的一起计算。我们发现第一项下指标几乎不重不漏且覆盖了 $[0,n]$，我们只要把几项填回去就可以用二项式定理化成 $2^n$ 抵消掉。

$f(l,r,m)$ 为 $g(l,r,m)$ 做贡献：$t=0,r\in[0,d]$，$r=0$ 时第一项等于第二项，没有贡献，所以此时贡献为 $\D-d\sum_k\binom{n}{\frac n2+k'd}$。

$f(l,r,m)$ 为 $g(l+1,r-1,m)$ 做贡献：$t=0,r\in[1,d-1]$，加上 $r=0$ 时第一项等于第二项，没有贡献，所以此时贡献为 $\D-d\sum_k\binom{n}{\frac n2+k'd}$。

$f(l,r,m)$ 为 $g(l+1,r,m)$ 做贡献：$t=1,r\in[0,d-1]$，正好填满，所以此时贡献为 $\D-d\sum_k\binom{n}{\frac{n+1}2+k'd}$。

$f(l,r,m)$ 为 $g(l,r-1,m)$ 做贡献：$t=-1,r\in[1,d]$，正好填满，所以此时贡献为 $\D-d\sum_k\binom{n}{\frac{n-1}2+k'd}$。

要注意必须四个项一起被计算或者一起不被计算，否则 $2^n$ 无法正确地抵消。

设 $K=2k'$，有 $K$ 是奇数。

考虑计算每个 $\binom{n}{m}$ 的贡献，其中 $m=\frac{n+t+x}2$，枚举 $t$。

上面的式子很简洁，可以看出来贡献为

线性筛因数和。

实现的时候注意要不要去掉 $d=1$ 的情况。