[OI][trick]利用对称去掉偏序关系

例题

problem

给定 $n$，序列 $A$，求

$$\sum_{i\le j} \left| A_i - A_j \right|$$

solution

这个 $i<j$ 的偏序很麻烦。

但是这个东西具有对称性。

具体地，

$$\left| x-y \right| = \left| y-x \right|$$

所以上个式子就可以很愉快的变成这个式子

$$\begin{aligned} \sum_{i\le j} \left| A_i - A_j \right| &= \frac{1}{2}(\sum _{i=1} ^n \sum_{j=1} ^n \left| A_i-A_j \right| - \sum_{i=1} ^n \left| A_i-A_i \right|)\\ &= \frac{1}{2} \sum _{i=1} ^n \sum_{j=1} ^n \left| A_i-A_j \right| \end{aligned}$$

尽管在这里这道题不是变的特别好做，但在某些题上有神力。

总结

对于有对称性的运算，我们可以考虑利用对称性，计算其所有等效的东西，在通过简单的运算去除多加的东西以简化运算。

运用

1. Luogu P5283 [十二省联考 2019] 异或粽子

Hint：利用异或的对称性，去掉偏序。虽然说你不用这个 trick 也行。

2. 考虑以下题目

问长为 $n$ 字符集大小为 $m$ 且不能有 $k$ 个相同字符连在一块的字符串有多少种。

Hint： $m$ 种字符对称。

题解往后会写。