2017-Sp120-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc和sub讨论A，cjb和sub开I，cjb上机敲了个FFT，sub上机I获得wa，之后yzc上机'''A1y37'''，cjb开出了E，上机'''E2y46'''。sub之后又wa了I，发现题意有偏差，精度又出了问题，'''I5y66'''。cjb上机敲了D的群论板子，yzc上机写高精度，'''D1y109'''。cjb丢了F给sub，yzc和sub一起搞J，都很难受，卡了很久过不了样例，cjb开了H，上机'''H1y149'''。之后cjb开了K，写好伪代码后在yzc帮助下'''K2y252'''.之前sub一度精神不振，还发现J题意读错了。之后sub上机'''J1y255'''，'''F1y274'''。之后sub试图写G，没写完。
== 总结 ==
=== chenjb ===
前面I太大意wa了太多，cjb读错了一次题，sub和yzc也读错了一次题浪费了很多时间很不应该，sub今天身体不太好，还好依然完成了8个题，如果前面处理好，按道理是应该要把G搞完的。非常喜欢这场的H，觉得非常妙，D题大力板子实在爽。
=== oipotato ===
'''acyclic'''是无环的意思!!!!!!!
=== subconscious  ===

== 题解 ==
 * A：显然题目等价于k-1个数字每个数字范围[1,n]，有且仅有一种数字出现奇数次的方案数。f[i][j]表示前i个数字，有j个数字出现奇数次的方案，转移显然，快速幂转移即可。

 * B：首先如果特征根都是正数，那么行列式是特征根的乘积必须>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. 其实只要拓扑排序判断一下是否存在一个环就好了。ps：还要判一下a[i][i]是否等于1....不然NO

 * C：

 * D：Schreier-Sims，把CalcTotalSize改成高精度即可。

 * E：每次把<k的点剔掉，更新度数，重复进行。剩下的一定有一个size>k+1的团，dfs随便输出即可。

 * F：对于每个箱子求凸包，求闵可夫斯基和，扫一遍即可。

 * G：

 * H：开k个vector维护答案，每次加入一个新值x，从k个vector中依次置换出自己的位置，如果当前vector是空或者最大值小于x，则放置最后且答案++。该过程和费用流增广是等价的。

 * I：Σa[i]b[j](a[i]-b[j])^2^，fft即可。

 * J：f[i][j]代表前面有i个可达位置，目前在j号位的方案数，大力dp转移即可。

 * K：枚举不同色对，用map套set或vector维护同色边数量，注意处理已有边和无该边的情况。

 * [https://wiki.icpc.camp/deep-dark-fantasy/20170404 DeepDarkFantasy]

流水账

开场各自看题，yzc和sub讨论A，cjb和sub开I，cjb上机敲了个FFT，sub上机I获得wa，之后yzc上机A1y37，cjb开出了E，上机E2y46。sub之后又wa了I，发现题意有偏差，精度又出了问题，I5y66。cjb上机敲了D的群论板子，yzc上机写高精度，D1y109。cjb丢了F给sub，yzc和sub一起搞J，都很难受，卡了很久过不了样例，cjb开了H，上机H1y149。之后cjb开了K，写好伪代码后在yzc帮助下K2y252.之前sub一度精神不振，还发现J题意读错了。之后sub上机J1y255，F1y274。之后sub试图写G，没写完。

总结

chenjb

前面I太大意wa了太多，cjb读错了一次题，sub和yzc也读错了一次题浪费了很多时间很不应该，sub今天身体不太好，还好依然完成了8个题，如果前面处理好，按道理是应该要把G搞完的。非常喜欢这场的H，觉得非常妙，D题大力板子实在爽。

oipotato

acyclic是无环的意思!!!!!!!

subconscious

题解

  • A：显然题目等价于k-1个数字每个数字范围[1,n]，有且仅有一种数字出现奇数次的方案数。f[i][j]表示前i个数字，有j个数字出现奇数次的方案，转移显然，快速幂转移即可。
  • B：首先如果特征根都是正数，那么行列式是特征根的乘积必须>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. 其实只要拓扑排序判断一下是否存在一个环就好了。ps：还要判一下a[i][i]是否等于1....不然NO
  • C：
  • D：Schreier-Sims，把CalcTotalSize改成高精度即可。
  • E：每次把k+1的团，dfs随便输出即可。
  • F：对于每个箱子求凸包，求闵可夫斯基和，扫一遍即可。
  • G：
  • H：开k个vector维护答案，每次加入一个新值x，从k个vector中依次置换出自己的位置，如果当前vector是空或者最大值小于x，则放置最后且答案++。该过程和费用流增广是等价的。
  • I：Σa[i]b[j](a[i]-b[j])2，fft即可。
  • J：f[i][j]代表前面有i个可达位置，目前在j号位的方案数，大力dp转移即可。
  • K：枚举不同色对，用map套set或vector维护同色边数量，注意处理已有边和无该边的情况。
  • DeepDarkFantasy
附加文件