AGC019 - F. Yes or No

解法

dp を立てる（配る DP の方が後々便利）

期待値ではなく総和を求める形にする

dp の遷移を分解し、式を整理する

$ \sum_{0 \leq i \leq N, 0 \leq j \leq M, i+j>0} \binom{n}{i} \times \binom{m}{i} \times \binom{n + m}{i + j} \times \frac{\max(i, j)}{i + j}が答えとなる

明らかに畳み込めそうな見た目だが$ \maxが邪魔なので大きい方を固定したい

分割統治 FFT（オンライン畳み込み）を使う -> $ O((N+M)\log^2(N + M))

atcoder::convolution は速いので、なんか通る

公式解説

グリッドの交差点に分数が書かれており、全ての経路について経路上の数の和を足し合わせるという問題になる

i+j を固定して順番に計算していくことにすると、差分がうまく計算できるらしい