\(O(n)\) 做法，目前 CF 最优解。
首先，考虑如何计算两个串的答案。
把奇数位置的值取反，那每次操作相当于 \(01\to10\) 或 \(10\to 01\)。于是当两个串 \(1\) 的个数相等时可以达成。
可以看作若干个 \(1\) 在一条链上移动到新的位置。答案为距离之和，把移动贡献均摊到每条边上，那每一条边的贡献就是 两个串\([1,i]\) 中的 \(1\) 个数的差值。
枚举 \([1,i]\) 中两个串 ? 处填写 \(0\) 的差值个数，那另一边 \([i+1,n]\) 中 ? 处填写 \(0\) 的差值个数确定。
如果确定了一边的 ? 处填写 \(0\) 的差值个数，那枚举第一个串中的 \(0\) 个数，一边的答案形如：
可以用范德蒙德卷积，化成一个组合数：
\[\binom{A+B}{B-d} \]另一边也相同，方案数就是两边乘起来。于是可以得到 \(O(n^2)\) 的做法。
// s[i]='0/1' -> s[i]=0/1.
// s[i]='?' -> s[i]=2.
For(i,0,2) as[i]=at[i]=bs[i]=bt[i]=0;
For(i,1,n) ++bs[s[i]],++bt[t[i]];
modint res=0;
For(i,1,n-1){
--bs[s[i]],--bt[t[i]];
++as[s[i]],++at[t[i]];
For(j,-n,n)
res+=C(as[2]+at[2],at[2]-j-as[0]+at[0])
*C(bs[2]+bt[2],bt[2]+j-bs[0]+bt[0])
*(j>0?j:-j);
}
观察这个式子，发现我们每次要求的形如：
\[\binom{A}{A_2-j}\binom{B}{B_2+j}|j| \]要求这个答案 \(n\) 次，并且每次的 \(A+B,A_2+B_2\) 为定值。
这个式子很像范德蒙德卷积，考虑把绝对值先拆成 \(|j|=(-j)+(2j)[j\ge 0]\).
第一部分要求 \(\binom{A}{A_2-j}\binom{B}{B_2+j}j\). 可以变成：
\[\binom{A}{A_2-j}\binom{B}{B_2+j}(B_2+j) - \binom{A}{A_2-j}\binom{B}{B_2+j}B_2 \]组合数收缩公式：
\[\binom{A}{A_2-j}\binom{B-1}{B_2+j-1}B - \binom{A}{A_2-j}\binom{B}{B_2+j}B_2 \]再用范德蒙德卷积：
\[\binom{A+B-1}{A_2+B_2-1}B-\binom{A+B}{A_2+B_2}B_2 \]于是可以单次 \(O(1)\)。
第二部分要求 \(\binom{A}{A_2-j}\binom{B}{B_2+j}j[j\ge 0]\).
用相同的方法变成：
\[\binom{A}{A_2-j}\binom{B-1}{B_2+j-1}B[j\ge 0] - \binom{A}{A_2-j}\binom{B}{B_2+j}B_2[j\ge 0] \]两部分是相同的，只考虑其中一部分，那就是要求：
\[\binom{A}{A_2-j}\binom{B}{B_2+j}[j\ge 0] \]\[\binom{A}{j}\binom{B}{A_2+B_2-j}[j\le A_2] \]由于 每次的 \(A+B,A_2+B_2\) 为定值，设 \(S_1 = A+B,S_2 = A_2+B_2\)。
考虑其组合意义，相当于有 \(S_1\) 个球，其中要放 \(S_2\) 个黑球，并且要求前 \(A\) 个球中只有 \(\le A_2\) 个黑球的方案数。
考虑在这条链上，从 \(i\to i+1\) 的时候，\(A\) 和 \(A_2\) 都只会有 \(O(1)\) 的变化。如果能 \(O(1)\) 移动 \(A±1,A_2±1\) 并且实时维护答案，那就能做了。
如果 \(A_2\to A_2+1\)，答案只需要加上新的贡献 \(\binom{A}{A_2+1}\binom{S_1-A}{S_2-(A_2+1)}\)。
如果 \(A\to A+1\)，答案会减少。再考虑其组合意义，减少的量就是“第 \(A_2+1\) 个黑球放在 \(A+1\) 位置”的方案数。于是答案只需要减去 \(\binom{A}{A_2}\binom{S_1-A-1}{S_2-A_2-1}\).
于是我们解决了 \(O(1)\) 移动端点的问题，整个问题可以 \(O(n)\) 解决。
顺便吐槽一句，为什么其他题解都用 dp 而不是组合数啊。