2017-Sp217-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，有人过G，三个人讨论了一下之后想让cjb抄三元环，cjb表示???决定上机手写暴力，'''G1y39'''。之后yzc上机'''K1y47'''，之后发现I的做法假了，sub会做M了，先上机写M，'''M2y79'''。cjb和yzc确认好做法之后，yzc上机写I，中途cjb会做E，sub会做I，抽空cjb上机'''E1y99'''，I 疯狂wa，各种查错，sub上机'''F1y177'''，最后'''I5y192'''。三个人一起讨论A，最后感觉是sam改一改，之后'''A2y212'''。sub试图做J，cjb和yzc试图开其他题，GG。最后rk 5，MIT 10，MSU 9，东大9，KAIST 8，NJU也是7不过罚时靠后。
== 总结 ==
=== chenjb ===
7个题之后只能躺在地上不能动弹啊？这个C以后是不是尽早写起来啊虽然其实不太会....A挺有意思的hhhh。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：直接延用SAM构造，不需要真的新建nq那个点。

 * B：cjb

 * C：sub

 * D：sub

 * E：给每条边随机一个值，然后每个点的值是邻边的异或；对于一组点，因为他要恰好联通块，所以所有点异或值为0才是YES，否则NO。

 * F：找出单个青蛙对第二个青蛙贡献的循环节，不超过1e6，就可以用前缀和加速第一个青蛙对第二个青蛙的贡献，二分答案即可。

 * G：建出生成树，非树边把这一段切掉，剩下每个联通块都能做到尽可能匹配，整除2加起来就好。

 * H：yzc

 * I：从后往前贪心，用哈希取最小的一段更新答案串。

 * J：除了头尾两个点外，其他的点符合p(x)=x*n mod (n*m-1)。枚举n*m-1的约数g，计算min k，g=g*n^k^ mod n*m-1，ans+=phi((n*m-1)/g)/k即可。注意特判n=m=1。

 * K：按S形，联通块大小递增的顺序构造，字母取MEX。

 * L：sub

 * M：内部和外部分别排序，外部相同的合并，然后从大到小每次选取合法的外部和内部，组合数即可。

流水账

出门各自看题，有人过G，三个人讨论了一下之后想让cjb抄三元环，cjb表示???决定上机手写暴力，G1y39。之后yzc上机K1y47，之后发现I的做法假了，sub会做M了，先上机写M，M2y79。cjb和yzc确认好做法之后，yzc上机写I，中途cjb会做E，sub会做I，抽空cjb上机E1y99，I 疯狂wa，各种查错，sub上机F1y177，最后I5y192。三个人一起讨论A，最后感觉是sam改一改，之后A2y212。sub试图做J，cjb和yzc试图开其他题，GG。最后rk 5，MIT 10，MSU 9，东大9，KAIST 8，NJU也是7不过罚时靠后。

总结

chenjb

7个题之后只能躺在地上不能动弹啊？这个C以后是不是尽早写起来啊虽然其实不太会....A挺有意思的hhhh。

oipotato

subconscious

题解

  • A：直接延用SAM构造，不需要真的新建nq那个点。
  • B：cjb
  • C：sub
  • D：sub
  • E：给每条边随机一个值，然后每个点的值是邻边的异或；对于一组点，因为他要恰好联通块，所以所有点异或值为0才是YES，否则NO。
  • F：找出单个青蛙对第二个青蛙贡献的循环节，不超过1e6，就可以用前缀和加速第一个青蛙对第二个青蛙的贡献，二分答案即可。
  • G：建出生成树，非树边把这一段切掉，剩下每个联通块都能做到尽可能匹配，整除2加起来就好。
  • H：yzc
  • I：从后往前贪心，用哈希取最小的一段更新答案串。
  • J：除了头尾两个点外，其他的点符合p(x)=x*n mod (n*m-1)。枚举n*m-1的约数g，计算min k，g=g*nk mod n*m-1，ans+=phi((n*m-1)/g)/k即可。注意特判n=m=1。
  • K：按S形，联通块大小递增的顺序构造，字母取MEX。
  • L：sub
  • M：内部和外部分别排序，外部相同的合并，然后从大到小每次选取合法的外部和内部，组合数即可。
附加文件