【OI】关于求 n 阶行列式
https://chuzihang714.github.io/post/za/
https://chuzihang714.github.io
用定义求其实很简单，首先我们观察一个三阶行列式，例如：
∣∣∣∣∣∣a1,1a2,1a3,1a1,2a2,2a3,2a1,3a2,3a3,3∣∣∣∣∣∣
此处先补充一下对角线法则：
- 对于二阶行列式：
实线表示相乘后加上这个值，虚线表示相乘后减去这个值。
那么解得x1x4−x2∗x3.
对于三阶行列式也是同理。
用对角线法则可求出其 =
a1,1∗a2,2∗a3,3 + a1,2∗a2,3∗a3,1 + a1,3∗a2,1∗a3,2 - a1,1∗a2,3∗a3,2 - a1,2∗a2,1∗a3,3 - a1,3∗a2,2∗a3,1
我们先设 axy 中的 x 为第几行 而后面的 y 则分别是 123 231 312 132 213 321 这不就是 1~n 的全排列吗？
同样这个性质也适用于解 n 阶行列式。
那么我们只需要求一下 1~n 的全排列再进行加减就行了。
那么问题就变成了如何确定这个值是要加上的还是要减去的，再进行观察，我们可以发现：
（这里简要提一下奇偶排列的区分：逆序对个数为奇数的排列就是奇排列，偶数即为偶排列。）
123 ， 231 ， 312 是三个偶排列。
132 ， 213 ， 321 是三个奇排列。
那么我们只需要用树状数组去求一下这个序列的逆序对就好了。
大致流程是：先求 1~n 的全排列，然后将这个排列 求个逆序对个数，若为奇数则减去，偶数则加上。
Tips:这里提一个比较简单的求全排列的方法：使用 next_permutation 具体使用方法见 这里 。
TheEnd.
