题解：CF2187D Cool Problem

题目传送门：洛谷 & codeforces。

题目简述

给定一个存在零一和问号的串 \(s\)，设 \(S=\{t\mid i\in\left[1, n\right]\cap\mathbb{Z},t_i\in\left\{\begin{matrix}\left\{0, 1\right\}\ \ \ \ s_i=? \\\left\{s_i\right\}\ \ \ \ else\end{matrix}\right.\}\)。
有 \(f(s)=\vec a\) 其中 \(a_i = \left\{\begin{matrix}0\ \ \ \ \ i=0\\x+a_{i-1}\ \ \ \ s_i=0\wedge i>0\\y-a_{i-1}\ \ \ \ s_i=1\wedge i>0\end{matrix}\right.\)，求 \(\sum_{t\in S}\sum_{i=1}^nf(t)_i\)。

思路

\(\sum_{i=1}^nf(t)_i\) 十分复杂，考虑先把这一部分化简掉。

由于\(a_i = \left\{\begin{matrix}0\ \ \ \ \ i=0\\x+a_{i-1}\ \ \ \ s_i=0\wedge i>0\\y-a_{i-1}\ \ \ \ s_i=1\wedge i>0\end{matrix}\right.\)
其中对于不同的 \(i\)，\(a_i\) 的递推和 \(s_i\) 相关，考虑找到一个不管 \(s_i\) 取多少都成立的 \(a_i\) 同 \(a_{i-1}\) 的关系式。

那么什么关系式会可能出现两种取值呢？容易想到小学二年级就学过的二次方程，那么 \(a_i\) 的两种不同取值就是方程的两个根。用双根式容易构造得

\[[a_i-(x+a_{i-1})][a_i-(y-a_{i-1})]=0 \]

展开a

\[a_i^2-(x+y)a_i+xy+(y-x)a_{i-1}-a_{i-1}^2=0 \]

因为要算 \(\sum_{i=1}^na_i\) 所以求和

\[\sum_{i=1}^na_i^2-(x+y)a_i+xy+(y-x)a_{i-1}-a_{i-1}^2=0 \]

分开

\[\sum_{i=1}^na_i^2-(x+y)\sum_{i=1}^na_i+nxy+(y-x)\sum_{i=1}^na_{i-1}-\sum_{i=1}^na_{i-1}^2=0 \]

变限（\(a_0 = 0\) 直接省略）

\[\sum_{i=1}^na_i^2-(x+y)\sum_{i=1}^na_i+nxy+(y-x)\sum_{i=1}^{n-1}a_i-\sum_{i=1}^{n-1}a_i^2=0 \]

组合一下

\[\left(\sum_{i=1}^na_i^2-\sum_{i=1}^{n-1}a_i^2\right)+\left[(y-x)\sum_{i=1}^{n-1}a_i-(x+y)\sum_{i=1}^na_i\right]+nxy=0 \]

化简（\(S_n = \sum_{i=1}^na_i\)）

\[a_n+(yS_{n-1}-xS_{n-1}-xS_{n-1}-yS_{n-1})+nxy=0 \]

其中

\[\begin{align*}yS_{n-1}-xS_{n-1}-xS_n-yS_n&=-x(S_{n-1}+S_n)+y(S_{n-1}-S_n)\\&=-x(2S_n-a_n)-ya_n\\&=-2xS_n+(x-y)a_n\\\end{align*} \]

带回

\[a_n-2xS_n+(x-y)a_n+nxy=0 \]

移项

\[a_n+(x-y)a_n+nxy=2xS_n \]

得到（\(S_n = \sum_{i=1}^na_i=\sum_{i=1}^nf(t)_i\)）

\[\sum_{i=1}^nf(t)_i=\frac{a_n+(x-y)a_n+nxy}{2x} \]