2018-Reconquista-T53
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
''' Petrozavodsk Summer 2011 - Moscow SU Unpredictable Contest '''
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001382 Opentrains]
== 流水账 ==
== 总结 ==
=== lsmll ===
又有比较严重的卡题，1.5h之后的下一次过题就是比赛结束前10min了..不过最后10min过了两题还是可以的，但是感觉我们对于这种思维难度较大的题还是不适应，才会出现卡题，还要多锻炼..
=== jsb ===
F题的戾气有点重。看到过的人挺多，就想搏一搏单纯形，单车变摩托。[[br]]
抄完板子，lsmll学长发现不小心简化了题意，其实还要再稍微拓展一下的。然后辛辛苦苦改了一个带vector版本的单纯形，光荣TLE了……[[br]]
后来凭着不舍的玄学改造，终于在快结束的时候搞过了F。lsmll学长也过了K，帅啊。[[br]]
感觉最近日常差二队两道？？？
=== lzw ===
前期还算顺利。后面感觉FH题都很诡异，或者说是思维上的锻炼有些不足。(F题的建模）
== 补题 ==
B [lzw]
C []
D [lzw]
G [jsb]
H [jsb]
== 题解 ==
[https://wiki.icpc.camp/deep-dark-fantasy/20170404 DeepDarkFantasy][[br]]
[B by lzw]首先如果特征根都是正数，那么行列式是特征根的乘积必须>0. 其次根据均值不等式行列式等于特征根的乘积<=(特征根之和/n)^n^ = (对角线上元素和/n)^n^ <= 1. 然后行列式又是整数，所以只能是取等号是1.
因此特征根也全部都是1. 所以我们只要判定矩阵的特征多项式是不是(x-1)^n^. 可以根据最小多项式来判断。数域P上的以矩阵A为根的多项式中，次数最低的首项系数为1的那个多项式，称为A的最小多项式。数域P上任意矩阵一定存在唯一的最小多项式，且这个最小多项式一定是特征多项式的因式。因此只要判断(x-1)^k^是否是特征多项式的因式。 其实只要判断(A-I)^n^是否是零矩阵，直接求会炸long long，转化成在以这个矩阵为邻接矩阵的图上，任意一个点走n步的方案数为0. 其实只要拓扑排序判断一下是否存在一个环就好了。[[br]]
[D by lzw]Schreier–Sims algorithm 抄个板子 + 高精度。[[br]]
[F,G,H] [https://www.cnblogs.com/jiangshibiao/p/8955409.html 6.1处]Contest Information
Petrozavodsk Summer 2011 - Moscow SU Unpredictable Contest
流水账
总结
lsmll
又有比较严重的卡题，1.5h之后的下一次过题就是比赛结束前10min了..不过最后10min过了两题还是可以的，但是感觉我们对于这种思维难度较大的题还是不适应，才会出现卡题，还要多锻炼..
jsb
F题的戾气有点重。看到过的人挺多，就想搏一搏单纯形，单车变摩托。[[br]]
抄完板子，lsmll学长发现不小心简化了题意，其实还要再稍微拓展一下的。然后辛辛苦苦改了一个带vector版本的单纯形，光荣TLE了……[[br]]
后来凭着不舍的玄学改造，终于在快结束的时候搞过了F。lsmll学长也过了K，帅啊。[[br]]
感觉最近日常差二队两道？？？
lzw
前期还算顺利。后面感觉FH题都很诡异，或者说是思维上的锻炼有些不足。(F题的建模）
补题
B [lzw]
C []
D [lzw]
G [jsb]
H [jsb]
题解
DeepDarkFantasy[[br]]
[B by lzw]首先如果特征根都是正数，那么行列式是特征根的乘积必须>0. 其次根据均值不等式行列式等于特征根的乘积<=(特征根之和/n)n = (对角线上元素和/n)n <= 1. 然后行列式又是整数，所以只能是取等号是1.
因此特征根也全部都是1. 所以我们只要判定矩阵的特征多项式是不是(x-1)n. 可以根据最小多项式来判断。数域P上的以矩阵A为根的多项式中，次数最低的首项系数为1的那个多项式，称为A的最小多项式。数域P上任意矩阵一定存在唯一的最小多项式，且这个最小多项式一定是特征多项式的因式。因此只要判断(x-1)k是否是特征多项式的因式。 其实只要判断(A-I)n是否是零矩阵，直接求会炸long long，转化成在以这个矩阵为邻接矩阵的图上，任意一个点走n步的方案数为0. 其实只要拓扑排序判断一下是否存在一个环就好了。[[br]]
[D by lzw]Schreier–Sims algorithm 抄个板子 + 高精度。[[br]]
[F,G,H] 6.1处