AGC019F Yes or No

看起来比已有的题解的最终结果都“简洁”一点？ 枚举一个时刻已知剩下几个 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 $$