计数好题，转换条件+转化贡献+组合数
首先题目的操作没有什么好的性质，考虑一个经典的 trick，将奇数位置上的数字取反，于是题目的操作变成 \(01\rightarrow 10\) 或 \(10 \rightarrow 01\)。这个操作的性质就是序列中 \(1\) 的总数不变，并且操作可以抽象成「使 \(1\) 在序列上移动」。
转化完条件，能使 \(s\) 和 \(t\) 相等的条件即 \(1\) 的个数相等。假设 \(1\) 的个数相等，此时考虑如何计算贡献。
设 \(s\) 序列中第 \(i\) 个 \(1\) 的位置为 \(a_i\)，\(t\) 序列中第 \(i\) 个 \(1\) 的位置为 \(b_i\)，那么答案就是 \(\sum|a_i-b_i|\)。
但是这么做在有问号的情况下并不好计算，考虑另一个 trick，我们将贡献转化成每一个空隙被跨过的次数。也就是对于每个 \(1\le i< n\) 的前缀 \(s_i\) 和前缀 \(t_i\) 的差值的绝对值（多出的部分一定需要从 \(i\rightarrow i+1\)）。
枚举每个间隙计算答案，考虑枚举左边的差值，不妨设 \(A\) 表示 \(s[1\sim i]\) 中的问号数量，\(B\) 表示 \(t[1\sim i]\) 的问号数量，此时一部分问号会变成 \(1\)，若 \(s\) 中问号变成 \(1\) 的数量为 \(j\)，两者差值为 \(d\)，则有方案数
\[\sum_j C_A^j C_B^{j+d} \]\[\sum_j C_A^j C_B^{B-j-d} \]这个形式可以用范德蒙德卷积，化成一个组合数：
\[C_{A+B}^{B-d} \]\([i+1,n]\) 的差值由 \([1,i]\) 的差值可以推出，方案数计算方法类似，最后两边方案数相乘再乘跨过次数就是差值为 \(j\) 时的贡献。
于是得到了 \(O(n^2)\) 的做法。
标签：sum,Grandmaster,CF1615F,差值,LEGOndary,问号 From： https://www.cnblogs.com/FireRaku/p/18091628