CF167E

题意：

给你一个有向无环图，其中没有入度的点为源点，没有出度的点为汇点。（保证源汇点数目相同）

考虑将源汇点两两匹配，用互不相交的路径将匹配的点对两两连接的所有方案。

将匹配视为二元组，按照源点升序排序，若得到的汇点逆序对个数式奇数，那么这种方案对答案的贡献案为 \(-1\)，否则对答案的贡献为 \(1\)。

数据范围：\(n \le 600\)。

思路：

首先，看到这个逆序对为偶数加一，为奇数减一的东西，第一反应一定是行列式的值。

令 \(f_{i,j}\) 为第 \(i\) 个源点到第 \(j\) 个汇点的路径条数。

发现如果不考虑路径不交这个条件，那行列式 \(f\) 的值就是答案。

发现所有路径有交的方案的贡献都是不用算的。

但是我们可以将一个路径有交的方案的字典序最小的那一对有交路径的第一个有交的位置将两条路径的后一半交换，这样一定唯一对应另一种路径有交的方案，并且那一种方案做这个变换得到的就是当前方案，这样就可以将路径有交的方案两两配对。

发现一对方案的汇点序列就是将两个不同位置交换得到，这样逆序对数一定奇偶性相反，所以每一对方案就直接抵消掉了，所以所有有交路径的贡献都被抵消，所以行列式 \(f\) 的值就是

原文地址：http://www.cnblogs.com/zzzYheng/p/16909547.html