ABC289H
令 \(f(i)\) 表示三个人在时刻 \(i\) 第一次相遇的概率，令 \(g(i)\) 表示三个人在时刻 \(i\) 相遇的概率。
\(f,g\) 都是令三个人初始位置是 \(A,B,C\) 的。
令 \(h(i)\) 为三个人开始在相同位置，在时刻 \(i\) 相遇的概率。
那么有转移式
\[f(i)=g(i)-\sum_{j=0}^{i-1}f(j)h(i-j) \]用一手生成函数
\[\sum_{i=0}^n f(i)x^i=\sum_{i=0}^n \bigg( g(i)x^i-\sum_{j=0}^{i-1}f(j)x^j\cdot h(i-j)x^{i-j}\bigg)\\ \sum_{i=0}^n f(i)x^i=\sum_{i=0}^n g(i)x^i-\sum_{i=0}^n\bigg(\sum_{j=0}^i f(j)x^j\cdot h(i-j)x^{i-j}\bigg)+\sum_{i=0}^n f(i)x^i\cdot h(0)x^0\\ F(x)=G(x)-F(x)H(x)+h(0)F(x)\\ F(x)=G(x)-F(x)(H(x)-1)\\ G(x)=F(x)H(x)\\ F(x)=\frac {G(x)}{H(x)} \]只要能求出 \(G,H\) 即可在 \(O(n\log n)\) 的时间内用多项式求逆解决。
这两个都是类似的，写成一般形式都可以刻画出 \(A,B,C\) 三个起始点。
强令 \(A=0,A\le B\le C\)，这个转化不会产生任何区别。
允许 \(+1\) 或 \(-1\)，改成允许 \(+2\) 或 \(+0\)，把下标 \(/2\) 变成允许 \(+1\) 或 \(+0\)。
枚举相遇的位置得到
\[\begin{align} g(i)&=\sum_{j=0}^{i}\binom {i}{j-A}\binom {i}{j-B}\binom {i}{j-C}\\ &=\sum_{j=0}^i\dfrac {(i!)^3}{(j-A)!(j-B)!(j-C)!(i-j+A)!(i-j+B)!(i-j+C)!}\\ \end{align} \]容易发现这是一个卷积式！
构造两个多项式卷起来即可。
时间复杂度：\(O(n\log n)\)
空间复杂度：\(O(n)\)
标签：cdot,sum,相遇,ABC289H,binom,bigg From： https://www.cnblogs.com/hellojim/p/17129735.html