T3
相当于有 \(n\) 个区间 \([a_{2i-1},a_{2i}]\)，然后令 \(x=a_0\)，依次 \(\forall i\in [1,n]\) ，如果 \(x<a_{2i-1},x=a_{2i-1}\)，如果 \(x>a_{2i},x=a_{2i}\) 。
考虑对于一个固定的 \(x\) 求答案。
注意到若区间 \([l,r]\) 满足 \(l<x<r\) ，我们删掉这个区间不影响答案，这些区间称为五小区间，那么删掉之后剩下了若干 \(r<x\) 的区间和若干 \(l>x\) 的区间。
假设 \(x\) 是某个区间的右端点，左端点类似。
考虑 \(x\) 在排列中的位置 \(i\)，那么要求 \((i,n]\) 这些区间都是无效区间 ，并且 \(i\) 左面第一个非无效区间的 \(l>x\) 或者第一个非无效区间的位置是 \(a_0\) 。
那么就可以计数，首先特判掉 \(a_0=x\) 的情况，此时 \(x=n\)，贡献 \(n!!\) 。
然后枚举极长的的无效区间后缀长度 \(i\)，然后把 \(x\) 所在区间插进去，
若 \(x\) 是右端点，贡献为：
其中 \(f_n\) 为把 \(n\) 个数排成 \(a_{2i-1}<a_{2i}\) 的方案数，显然有递推 \(f_{n}=\binom{n}{2}f_{n-2}\)，展开后 \(f_n=\frac{n!}{2^{n/2}}\)
推一波式子：
\[\sum_i \binom{x}{i}\binom{2n-x}{i}i!i!\binom{2n-x-i}{2}(x-i)(i+1)f_{2n-2i-3} \]\[\sum_i \frac{x!(2n-x)!}{(x-i)!(2n-x-i)!}\binom{2n-x-i}{2}(x-i)(i+1)f_{2n-2i-3} \]\[x!(2n-x)!\sum_i \frac{(2n-x-i)(2n-x-i-1)}{(x-i)!(2n-x-i)!2^{n-i-1}}(x-i)(i+1)(2n-2i-3)! \]若 \(x\) 为区间左端点，贡献是类似的，为：
\[x!(2n-x)!\sum_i \frac{(x-i)(x-i-1)}{(x-i)!(2n-x-i)!2^{n-i-1}}(2n-x-i)(i+1)(2n-2i-3)! \]加起来得到：
\[x!(2n-x)!\sum_i \frac{(x-i)(2n-x-i)(2n-2i-2)!}{(x-i)!(2n-x-i)!2^{n-i-1}}(i+1) \]\[x!(2n-x)!\sum_i \frac{(2n-2i-2)!}{(x-i-1)!(2n-x-i-1)!2^{n-i-1}}(i+1) \]\[x!(2n-x)!\sum_{i>0} \frac{(2n-2i)!}{(x-i)!(2n-x-i)!2^{n-i}}i \]\[\frac{1}{2^n}x!(2n-x)!\sum_{i>0} \binom{2n-2i}{x-i}2^{i}i \]还有一种情况是所有区间都是无效区间，此时也满足 \(x=n\)，贡献也是好算的，我们只需要处理上面的求和式。
设
\[f_{x,p,q}=\sum_{i=1}^{n-1}i^p2^i\binom{2n-2i-q}{x-i} \]其中 \(p,q\in \{0,1\}\) 。
我们考虑从 \(f_x\) 推到 \(f_{x+1}\) ，我们可以得到如下式子：
\[\sum_{i=1}^{n-1}i^p2^i\binom{2n-2i}{x-i}=\sum_{i=1}^{n-1}i^p2^i\binom{2n-2i-1}{x-1-i}+\sum_{i=1}^{n-1}i^p2^i\binom{2n-2i-1}{x-i} \]即 \(f_{x,p,0}=f_{x-1,p,1}+f_{x,p,1}\) 。
\[\sum_{i=1}^{n-1}i2^i\binom{2n-2i-1}{x-i}=\frac{1}{2}\sum_{i=2}^{n}(i-1)2^i\binom{2n-2i+1}{x-i+1} \]\[\sum_{i=1}^{n-1}i2^i\binom{2n-2i-1}{x-i}=\frac{1}{2}\sum_{i=2}^{n}(i-1)2^i\binom{2n-2i}{x-i}+\frac{1}{2}\sum_{i=2}^{n}(i-1)2^i\binom{2n-2i}{x-i+1} \]\[2\sum_{i=1}^{n-1}i2^i\binom{2n-2i-1}{x-1-i}=\sum_{i=2}^{n}(i-1)2^i\binom{2n-2i}{x-1-i}+\sum_{i=2}^{n}(i-1)2^i\binom{2n-2i}{x-i} \]\[2f_{x-1,1,1}=f_{x-1,1,0}-f_{x-1,0,0}+f_{x,1,0}-f_{x,0,0} \]此外还有：
\[\sum_{i=1}^{n-1}2^i\binom{2n-2i-1}{x-i}=\frac{1}{2}\sum_{i=2}^{n}2^i\binom{2n-2i+1}{x-i+1} \]\[2\sum_{i=1}^{n-1}2^i\binom{2n-2i-1}{x-i}=\sum_{i=2}^{n}2^i\binom{2n-2i}{x-i}+\sum_{i=2}^{n}2^i\binom{2n-2i}{x-i+1} \]\[2\sum_{i=1}^{n-1}2^i\binom{2n-2i-1}{x-1-i}=\sum_{i=2}^{n}2^i\binom{2n-2i}{x-1-i}+\sum_{i=2}^{n}2^i\binom{2n-2i}{x-i} \]即
\[2f_{x-1,0,1}=f_{x-1,0,0}-2\binom{2n-2}{x-2}+f_{x,0,0}-2\binom{2n-2}{x-1} \]有了四个式子，我们就可以 \(O(n)\) 递推了。
标签：frac,sum,魔法,2i,区间,2n,binom From： https://www.cnblogs.com/jesoyizexry/p/18019792