G Greetings Souvenir 再更新一下，造了一些hack数据对拍，拿了三份代码对拍，给出几份hack数据输出彼此之间都有一致的数据也有不一致的，说明至少四支队伍可以hack掉三只队伍!!!! 61 2 1 2 56 5 2 1 2 3顶不住也给我顶：6空白：5吃顿好的：6ContestinSurgery ：段错误 66 4 5 2 13 1 6 2 5 4顶不住也给我顶：4空白：6吃顿好的：6ContestinSurgery ：段错误 81 2 2 2 2 1 73 2 7 3 2 3 5 1顶不住也给我顶：6空白：6吃顿好的：8ContestinSurgery ：段错误 网络流...

这里给出一种容斥+多项式的做法 复杂度为是n^2/2 大家一般是容斥+背包啊，我觉得这里多项式也蛮好写的。 容斥应该不用多说了，设为第i个球合法的情况。套一套下面两个公式。  我们要求的是第二个公式的左半，用第一个公式带入第二个公式的右边第二项。  所得公式的右半边从左向右数第i项(不考虑符号)，表示n个球里面，任选i个不球，这i个球不合法，其他球任意（可合法也可不合法）的方案数。 其他球任意的方案数是种，那么剩下的i个球不合法的方案数是多少嘞。用下生成函数的方法来表示，第i个箱子有cnt[i]个候选的不合法球，可以选一个不合法球，生成函数表示就是(1+cnt[i]*x)，全部n个箱子对应的生...

研究了一天终于会写了，故在自己研究并ac后简略提供下解题思路。 官方题解中，"这样我们就转化为k堆独立的硬币问题"是最让我迷惑的地方，这里错了，应改为"转化成n堆独立的硬币问题"。IOI2009中国集训队论文 有一篇关于SG函数的论文中提出的翻硬币问题就是本题的背景。 翻硬币问题可以转化为若干0加一个1的串的子游戏，而这类题目属于Multi-SG问题，每次翻硬币等价于把一个子游戏又分为更多的子游戏，子游戏的sg函数为所有子子游戏的异或和。 比如样例1001001001，可以转化为四个子问题。1000100000010000000001所以只需要算出上述四个子问题的SG函数异或和是否为0即可 那...