【Codeforces 176E】Wizards and Bets

相关链接

题目传送门:http://codeforces.com/problemset/problem/167/E
神犇题解:http://blog.csdn.net/popoqqq/article/details/45046545

吐槽

神™套路题,考试考这个也是简直了
出题人你能不能良心一点 (╯‵□′)╯︵┻━┻

还有一个高一神犇各种瞎搞给做出来了……
牛逼!我就服你!

解题报告

我们可以把给的出发点到目标点配对之后重新标号
于是我们可以看成是一个置换
然后我们考虑在每一个交叉的位置交换那两条路径的目标点
于是这个方案的置换奇偶性一定改变

然后我们考虑如果一套路径方案交叉了奇数次,那么这是一个奇置换,算行列式时系数为$-1$
如果一套路径的方案交叉了偶数次,那么这是一个偶置换,算行列式的时候系数为$1$
这刚好和容斥的系数对上!于是我们算出行列式就相当于用容斥算出了答案

现在回到行列式的定义:$|A|= \sum\limits_{\sigma\in Sn}{{\mathop{\rm sgn}}(\sigma)\prod\limits_{i= 1}^n{{a_{i,\sigma(i)}}}}$
系数已经没有问题了,那么看方案数的统计,我们发现设$f_{i,j}$为$i \to j$的方案数
放到矩阵的对应位置上,刚好又能对上方案数,于是什么都对上了,这题算个行列式就完了