2017-Sp318-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：M对F是拆分数dp，F对M是序列dp+polya，int128打表。

 * B：每次狂赌，模拟。

 * C：每次取一个相邻逆序对交换，然后对交换的点疯狂地和其他相同数字交换，开头和结尾再加上所有相同数字互相的交换，再加点随机就过了。

 * D：lct维护lca

 * E：

 * F：质因子多的赢。

 * G：求出每个点后继最小值，值小的优先级高，优先队列贪心维护即可。

 * H：

 * I：能区分的子串一定是SAM上right集合不同的，SAM的接受态是最后一个节点的所有parent树上的祖先，问题转化为从S出发至多多少条路径不会经过相同的状态，这个前提下要求路径总长度最长，建图跑费用流，把spfa魔改成优先队列就能艹过去了，因为建图本质上是个dag。

 * J：答案显然是入度为0的点中的某个，随机序列，按先来后到染色确定点的控制区域大小，不断更新答案，最后再跑一次算出真实控制区域即可。实际上随着科技进步，bitset只会有空间问题，分块bitset也能通过。

流水账

chenjb

oipotato

subconscious

题解

• A：M对F是拆分数dp，F对M是序列dp+polya，int128打表。
• B：每次狂赌，模拟。
• C：每次取一个相邻逆序对交换，然后对交换的点疯狂地和其他相同数字交换，开头和结尾再加上所有相同数字互相的交换，再加点随机就过了。
• D：lct维护lca
• E：
• F：质因子多的赢。
• G：求出每个点后继最小值，值小的优先级高，优先队列贪心维护即可。
• H：
• I：能区分的子串一定是SAM上right集合不同的，SAM的接受态是最后一个节点的所有parent树上的祖先，问题转化为从S出发至多多少条路径不会经过相同的状态，这个前提下要求路径总长度最长，建图跑费用流，把spfa魔改成优先队列就能艹过去了，因为建图本质上是个dag。
• J：答案显然是入度为0的点中的某个，随机序列，按先来后到染色确定点的控制区域大小，不断更新答案，最后再跑一次算出真实控制区域即可。实际上随着科技进步，bitset只会有空间问题，分块bitset也能通过。