题解：CF2135E2 Beyond the Palindrome (Hard Version)

· · 题解

\xdef\0{\texttt{0}}\xdef\1{\texttt{1}}\xdef\D{\displaystyle}

E1

反射容斥入门。

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

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

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

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

答案可以表示为

Ans=\sum_{l\le0}\sum_{r\ge0} g(l,r,l+r)

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

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

g(l,r,m)=f(l,r,m)-f(l-1,r,m)-f(l,r+1,m)+f(l-1,r+1,m)

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

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

考虑翻转对起点的影响。

\begin{aligned} (0,y)&\xrightarrow{L}(0,2l-y)\xrightarrow{R}(0,y+2(r-l))\\ (0,y)&\xrightarrow{R}(0,2r-y)\xrightarrow{L}(0,y+2(l-r))\\ \end{aligned} 设 $ways((x,y))$ 表示从 $(x,y)$ 走到终点 $(n,m)$ 的方案数，这题中 $x$ 一定为 $0$，后面直接省略，简单的推导我们可以得到 $ways((x,y))=\binom{n}{\frac{n+m-y}2}$。 $$ f(l,r,m)=ways(I)-ways(L)-ways(R)+ways(LR)+ways(RL)-ways(LRL)-ways(RLR)+\dots $$ $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$ 可取所有整数，为了让式子好看一点，做一点变换。 $$ f(l,r,m)=\sum_k\binom{n}{\frac{n+m}2+k(r-l)}-\binom{n}{\frac{n+m}2+k(r-l)-r} $$ 但是做到这里还是没法通过 E1。 注意 $m=l+r+t=t-(r-l)+2r,t\in\{-1,0,1\}$，定义 $k'=k-\frac12$。 $$ f(l,r,l+r+t)=\sum_k\binom{n}{\frac{n+t}2+k'(r-l)+r}-\binom{n}{\frac{n+t}2+k'(r-l)} $$ 枚举 $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$ 无法正确地抵消。 [E1 submission](https://codeforces.com/contest/2135/submission/346409276) ## E2 设 $K=2k'$，有 $K$ 是奇数。 考虑计算每个 $\binom{n}{m}$ 的贡献，其中 $m=\frac{n+t+x}2$，枚举 $t$。 上面的式子很简洁，可以看出来贡献为 $$ \sum_{K,d}[dK=x][2\nmid K]d $$ 线性筛因数和。 实现的时候注意要不要去掉 $d=1$ 的情况。 [E2 submission](https://codeforces.com/contest/2135/submission/346428081)