这明摆着是一道计数题,计数题能用些啥?dp?我不会拦你的。多项式?生成函数?没错,这道题就是生成函数。
不能难发现,深度=祖先数+1,而\(i\)是\(j\)的祖先,当且仅当对任意在\(i\)和\(j\)之间的整数\(k\),均满足\(a_i<a_k\)。
设\(f_{|i-j|,k}\)表示\(i\)是\(j\)的祖先时,逆序对数为\(k\)的方案数,则其生成函数
\[
\LARGE F_{|i-j|}(x)=\begin{cases}\prod_{t=0,t\neq j-i}^{n-1}\sum_{p=0}^tx^p(i<j)\\x^{i-j}\prod_{t=0,t\neq i-j}^{n-1}\sum_{p=0}^tx^p(i>j)\end{cases}
\]
方法:考虑先往序列里面插入所有下标在\(i\)到\(j\)之间的数(不含\(i\)),共\(|i-j|\)个数,再插入\(a_i\),再插入剩下的数。
然后,
\[
\LARGE F_{|i-j|}(x)=\begin{cases}\frac{\prod_{t=1}^n\frac{1-x^t}{1-x}}{\frac{1-x^{j-i}}{1-x}}(i<j)\\x^{i-j}\frac{\prod_{t=1}^n\frac{1-x^t}{1-x}}{\frac{1-x^{i-j}}{1-x}}(i>j)\end{cases}
\]
先求出\(\prod_{t=2}^n\frac{1-x^t}{1-x}\),再乘或除\(1-x^p\)就可以得到\(F_p(x)\),取第\(k\)项和第\(k-p\)项系数。
注意:用\(\text{FFT}\)会\(\color{red}{\text{TLE}}\),可以暴力乘或除。