算法

考虑转化
每个点 \(p_i\) 在一个平面直角坐标系中表示为点 \((i, p_i)\)

于是转化为一个棋盘问题, 即每一个点不能在 同一行 / 同一列
\(a\) 数组的限制相当于在左下角为 \((0, 0)\), 右上角为\((i, i)\) 中的正方形中, 有 \(a_i\) 个棋子

于是在每一次加入的时候, 都只能在一个 L 型区域的符合要求的地方加入

例如此时就只能在红色区域加入

于是可以分类讨论(此处 \(a_i\) 均为差分数组)

• 当 \(a_i = 0\), 则代表没有增加任何点对, 答案不变
• 当 \(a_i = 1\), 则代表增加了一个点对, 有 \(2 \times i - 1 - 2 \times a_{i - 1}\) 种可能的选择, 将其乘入答案
• 当 \(a_i = 2\)，则代表增加了两个点对, 每个点有 \(i - 1 - a_{i - 1}\) 种可能的选择, 将其的平方乘入答案

代码

总结

计数类型的题目, 不仅可以用

• dp
• 直接计算

还可以使用

• 转化法