由于周末事情太多所以没有进行。

对偶图

本周无

林星涵：

陶吟翔：

郭衍培：

给定n个数，将这些数分为两个集合，使得这两个集合的数总和之差最小。n个数的给出方式是给定一个p和$a_1,\ldots,a_n$，这n个数是$p^{a_1},p^{a_2},\ldots,p^{a_n}$。结果模$10^9+7$题目链接

结论1：若一个数a大于一个集合A中的所有数，且A中的所有数之和大于a，则存在A的一个子集，该集合所有数之和等于A。且该子集可以由A中前n大的数组成。

结论2：用p个$p^{a_i-1}$替换$p^{a_i}$，结果一定更优

由结论1，最大的数a在两个集合中的出现次数之差不超过1（否则一定不优）。且若差为1，则另一个集合要么包含其余全部小于a的数（其余数之和仍小于a）；要么另一个集合的前n大数之和等于a。若为后者，由结论2，此时最优策略是将小于a的前n大数放进另一个集合。接下来，可以重复上述过程，直到小于a的所有数之和小于a。 实现时，可以通过模一些大的质数（只模一个1e9+7会被卡）判断是否相等。