10.20
gugugu
10.21
gugugu...
10.22
abc290f
发现实际可能对答案造成贡献的序列的和为\(2n-2\)，于是我们通过插板法计算答案：
\[\sum_{k=1}^n\dbinom{n}{k}\dbinom{n-3}{k-2}(n-k+1)
\]
然后化简，通过吸收恒等式和范德蒙德卷积变为：
\[(n-1)\dbinom{2n-3}{n-1}-(n-3)\dbinom{2n-4}{n-3}
\]
预处理阶乘及逆元可以做到\(O(1)\).
P2757
n方过五十万，暴力碾标算极其巧妙的一个转化。
题目中说序列是一个排列，也就是说无须担心值域和重复。
发现题目中所说的约束等价于长度等于3的。然后我们根据套路，从中间数开始计算。发现如果存在\(a_i\)满足\(a_i-k\)与\(a_i+k\)分别位于\(a_i\)两侧，那么这个子序列就是满足条件的。然后我们将他转换到是否被扫描过。如果满足条件，那么\(vis_{a_{i-k}}\ne vis_{a_{i+k}}\).如果连续一段\(k\)都不满足条件，那么这一段序列就是回文的。通过字符串哈希和线段树维护。
暴力的话，直接判断是否存在存在\(a_i\)满足\(a_i-k\)与\(a_i+k\)分别位于\(a_i\)两侧即可。加个卡时就能过。