AGC019F Yes or No
Elegia
2022-01-04 23:00:53
看起来比已有的题解的最终结果都“简洁”一点?
枚举一个时刻已知剩下几个 T/F,容易得到如下和式
$$
\frac 1{\binom{n+m}n}\sum_{i+j\ge 1} \binom{i+j}{i} \binom{n-i +m-j}{n-i} \cdot \frac{\max(i,j)}{i+j}
$$
固定 $k=i+j$,我们有
$$
\begin{aligned}
&= \frac 1{\binom{n+m}n} \sum_{k=1}^{n+m} \sum_i \frac{\max(i,k-i)}{k} \binom k i \binom {n+m-k}{n-i}\\
&= \frac 1{\binom{n+m}n} \sum_{k=1}^{n+m} \sum_i \max \left\{\binom{k-1}{i-1}, \binom{k-1}i \right\} \binom {n+m-k}{n-i}\\
&= \frac 1{\binom{n+m}n}\sum_{k=1}^{n+m} \left[\sum_{i\ge k/2} \binom{k-1}{i-1} \binom {n+m-k}{n-i}\right]
+ \left[ \sum_{i < k/2} \binom {k-1}i \binom{n+m-k}{n-i} \right]
\end{aligned}
$$
对于左侧求和,强行加上一个 $\binom{k-1}{i}$ 再减掉。得到
$$
\begin{aligned}
&= \frac 1{\binom{n+m}n}\sum_{k=1}^{n+m} \left[\sum_{i\ge k/2}\left[ \binom{k-1}{i-1} - \binom{k-1}{i} \right]\binom {n+m-k}{n-i}\right]
+ \left[ \sum_{i} \binom {k-1}i \binom{n+m-k}{n-i} \right]\\
&= \frac 1{\binom{n+m}n}\sum_{k=1}^{n+m} \left[\sum_{i\ge k/2}\left[ \binom{k-1}{i-1} - \binom{k-1}{i} \right]\binom {n+m-k}{n-i}\right] + \binom{n+m-1}{n}\\
&= m + \frac 1{\binom{n+m}n}\sum_{k=1}^{n+m} \sum_{i\ge k/2}\left[ \binom{k-1}{i-1} - \binom{k-1}{i} \right]\binom {n+m-k}{n-i}
\end{aligned}
$$
假设有生成函数 $f(x) = \sum_{n} a_n x^n$,我们有
$$
[t^0] \frac {f(x/t)t^k}{1-t} = \sum_{n\ge 0} a_n x^n [t^0] \frac{t^{k-n}}{1-t} = \sum_{n\ge k} a_nx^n
$$
运用该式,我们得到
$$
\begin{aligned}
[i\ge k/2] \cdot \left[\binom{k-1}{i-1} - \binom{k-1}i\right] &= [i\ge \lceil k/2\rceil] \cdot [x^i] (x-1)(x+1)^{k-1}\\
&= [t^0][x^i] \frac{(x/t-1)(x/t+1)^{k-1} t^{\lceil k/2 \rceil}}{1-t}
\end{aligned}
$$
问题关键转为演算
$$
\sum_{k=1}^{n+m} \frac{(x/t-1)(x/t+1)^{k-1} t^{\lceil k/2 \rceil}}{1-t} \cdot (x+1)^{n+m-k}
$$
我们一般来说都希望让把有限和改成无限和,对这个问题而言,由于最后我们要提取 $[x^n]$,所以 $\lceil k/2 \rceil>n$ 的时候肯定没有贡献,也就是 $k>2n$ 的时候。如果 $2n\le m+n \iff n \le m$,就可以直接改成自然求和了。由于从原式来看关于 $n,m$ 对称,所以 $n>m$ 的时候直接在最初交换 $n,m$ 进行求解即可。
$$
\begin{aligned}
&=\sum_{k\ge 1} \frac{(x/t-1)(x/t+1)^{k-1} t^{\lceil k/2 \rceil}}{1-t} \cdot (x+1)^{n+m-k}\\
&= \frac{(x/t-1)(x+1)^{n+m}}{(1-t)} \sum_{j\ge 0} \left( \frac{(x/t+1)^{2j}}{(x+1)^{2j+1}} + \frac{(x/t+1)^{2j+1}}{(x+1)^{2j+2}} \right) t^{j+1}\\
&= \frac{(x/t-1)(x+1)^{n+m}}{(1-t)} \sum_{j\ge 0} \left(\frac 1{x+1} + \frac{x/t+1}{(x+1)^2}\right) t \cdot \frac{(x/t+1)^{2j}t^j}{(x+1)^{2j}}\\
&= \frac{(x/t-1)(x+1)^{n+m-2} (x+1+x/t+1)}{(1-t)} \frac{1}{1-\frac{(x/t+1)^2t}{(x+1)^2}}\\
&= \frac{(x/t-1)(x+1)^{n+m} (xt+2t+x)}{(1-t)} \frac{1}{t(x+1)^2-(x+t)^2}\\
&= \frac{(x/t-1)(x+1)^{n+m} (xt+2t+x)}{(1-t)} \frac{1}{(t-x^2)(1-t)}\\
&= \frac{(x+1)^{n+m} (x^2/t^2+x^2/t + x/t - x - 2)}{(1-t)^2} \frac{1}{1-x^2/t}
\end{aligned}
$$
将其提取系数,得到
$$
\begin{aligned}
[x^n][t^0] \cdots &= \sum_{k\ge 0} [x^{n-2k}][t^k] \frac{(x+1)^{n+m} (x^2/t^2+x^2/t + x/t - x - 2)}{(1-t)^2}\\
\Sigma &= \sum_{k\ge 0} S_{n-2k-2,k+2} + S_{n-2k-2,k+1} - 2S_{n-2k,k} + S_{n-2k-1,k+1} - S_{n-2k-1,k}\\
S_{j,k} &= [x^n][t^k] \frac{(x+1)^{n+m}}{(1-t)^2}\\
&= \binom{n+m}j\cdot(k+1)\\
\Sigma &= \sum_{k\ge 0} \binom{n+m}{n-2(k+1)}(2k+5) - 2\binom{n+m}{n-2k}(k+1) + \binom{n+m}{n-2k-1}\\
&= \left[\sum_{k\ge 0} \binom{n+m}{n-2k-1}\right] + \sum_{k\ge 0} \binom{n+m}{n-2k-2}\\
&= \sum_{k=0}^{n-1} \binom{n+m}{k}
\end{aligned}
$$
综上,不妨令 $n\le m$ 后,答案为
$$
m + \frac 1{\binom{n+m}n}\sum_{k=0}^{n-1} \binom{n+m}k
$$