奥林匹克五子棋

from qmqmqm

算法一

答案只与最后的棋盘有关。暴力枚举所有的棋盘然后判断是不是符合条件。

最终复杂度是 $O(nm{2}^{nm})$。可以获得 30 分。

算法二

如果对于一组 $n,m,k$ 如果有解，那么对于 $n,m,k+1$ 也有解。

明显如果 $k=1$，那先手随便下一个子就赢了，所以无解。

当 $min(n,m)=1$ 时，如果 $k=2$,那么双方只要棋子间隔分布，就是可行解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法三

当 $min(n,m)<k$ 时，斜线方向是明显永远符合条件的。所以我们采取像黑白染色那样，这样在横竖方向上最长连续段都是 $1$，明显是符合条件的解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法四

当 $n,m\ge 2$ 时，可以证明如果 $k=2$ 是无解的。

具体来说考虑 $(1,1),(1,2),(2,2)$ 三个点，由抽屉原理得其中必定有两个点同色，那么他们就成了一个长为 $2$ 的同色连续段。

所以我们来考虑 $k=3$ 的情况。

可以想到，$k=3$ 一定不会在内部有一个 $2\times 2$ 的同色块，否则这个块的下方三个位置就会形成一个长为 $3$ 的同色连续段。进而一个同色的 L 形也不能存在，因为其上方三个斜向位置都必须和它颜色不同，从而形成一个长为$3$的同色连续段。

这样一来，构造必须是一些 $1\times 2$ 的条间隔分布。观察发现，这个构造符合题目中的所有条件。再根据上边的结论，$k>3$ 的情况也解决了。

最终复杂度是 $O(nm)$。结合算法二可以获得 100 分。

奥林匹克环城马拉松

from ftiasch，题解 from C_SUNSHINE

算法一

首先我们判断掉无解的情况，即存在一个点度数为奇数，此时方案数为 $0$。

从 $1$ 号点开始搜索欧拉回路，只要记录当前在哪和 $u,v$ 之间还有几条边没有走就好了，状态数是所有 $t_i$ 的积乘以 $n$，每次枚举下一步往哪走，可以从将要走的路上选一条未走过的边来走，并乘以这条路上剩余的边数，这样转移复杂度是 $O(n)$ 的，可以得到 $20$ 分。

算法二

注意到树的每一条边数目都是偶数，且走过去和走回来的次数各占一半，令一个点的度数 $de{g}_x$ 为走入这个点的次数即这个点相邻边权和除以$2$。

首先先要确定每一条边的方向，这个其实就是在每一组重边中选一半向下，另一半向上，所以是 $\prod (\genfrac{}{}{0ex}{}{t_i}{t_i/2})$。

那么确定方向之后，欧拉回路如何计数呢？

我们有一个简单粗暴的方法，在每个点上对于每一条入边为它指定一个后继出边，这样边与边之间就连起来了，由于 $de{g}_x$ 条入边和出边的匹配方案数是 $de{g}_x!$，于是答案就是 $\prod de{g}_x!$。

妈呀我怎么过不了样例啊……

可以发现这样确定出来的不是欧拉回路，而是若干个环并在一起。

继续思考，我们可以使用一些类似“骨架”的东西来连接整个欧拉回路。而在连通图中，树是一个不错的选择。

我们令欧拉回路从 $1$ 号点开始走，把最后一次经过除 $1$ 号点以外的点时走的出边拿出来作为特殊边。那么除了 $1$ 号节点以外每个节点有一条出边，并且由于是最后一次，不会出现环。于是这些特殊边构成了一棵以 $1$ 为根的树。

怎么统计这棵树呢？只要从向上走的边上拉一条出来就好了，方案数是 $\prod t_i/2$

确定了最后一条出边之后找欧拉回路的过程其实也不难，对于一个点 $x(x>1)$，前 $de{g}_x-1$ 次可以非特殊出边中任意挑选，最后一次只能走特殊出边，方案数是 $(de{g}_x-1)!$。对于 $1$ 号点来说没有特殊边的限制方案数仍然是 $de{g}_1!$。

于是方案数变成了 $de{g}_1!\prod _{x>2}(de{g}_x-1)!$，再乘上其他系数……妈呀我怎么还是过不了样例啊。

注意题目要求循环同构算同一种方案，但是你强制起点是 $1$，而 $1$ 在欧拉序列中可能出现了多次，于是你就统计了多次。

解决办法也很简单，$1$ 在欧拉序列中出现的次数恰好是 $de{g}_1$，除掉即可，这样最后一部分方案数变成了 $\prod (de{g}_x-1)!$。

时间复杂度 $O(n)$，期望得分 $20$ 分，结合算法一可获得 $40$ 分。

算法三

观察树上的结论，我们会发现有向图的欧拉回路计数问题是有一个通用公式的：

$$T\cdot \prod (de{g}_x-1)!$$

其中 $T$ 是以某个节点为根的树形图数目。

于是问题就变成了给图定向。

考虑一个环的情况，由于 $t_i\le {10}^4$，我们可以直接枚举在环上转了几圈，那么每条边往两个方向走的次数都能计算出来。

接下来就是求环的树形图数目了。

对于 $n=m=3$ 的情况显然可以手算，其余的情况，注意到树只比环少一条边，那么枚举那条边断开就好了。

时间复杂度 $O(t_{i}n)$，期望得分 $30$，结合算法一二可获得 $70$ 分。

算法四

环的问题解决之后，环套树问题就变得十分容易了。事实上，枚举任意一条环边正着走了多少次，根据有向图欧拉序列条件式 $indegre{e}_x=outdegre{e}_x$，就可以直接给无向边定向，定向的方案数直接用组合数计算就好了，例如 $t_i$ 条无向边有一侧是 $s_i$ 条，方案数就是 $\prod (\genfrac{}{}{0ex}{}{s_i}{t_i})$。

第二步就是树形图计数，这一步只要把环上的树形图计数和每个点的外向树树形图计数直接乘起来即可。

最后乘以 $\prod (de{g}_x-1)!$ 即可。

时间复杂度 $O(t_{i}n)$，期望得分 $100$ 分。

奥林匹克数据结构

from ppfdd，题解 from matthew99

算法一

直接按照题意模拟，时间复杂度$O(n\sum {m_i}^2)$，加上一些小优化很容易做到$O(n\sum m_i)$。

算法二

考虑KMP的过程，我们同样考虑对b串建出KMP中的fail数组。那么我们发现，只需要将KMP中判断两个数相等的操作改成判断只要最后一个数字在整个序列中的名次相同即可。

用主席树实现可能会有常数问题。我们发现，我们只需要用树状数组预处理出b串中每个位置在它前面的所有数中的名次。然后再用树状数组维护当前的border，由于在KMP中border是单调的，所以每次border变化的时候暴力修改即可。

时间复杂度$O((n+\sum m_i)\log n+\sum m_i\log m_i)$。

算法三

考虑多串匹配，显然就是将KMP改成AC自动机，转移就是考虑下一个数在当前点到根的路径上的所有数中的名次，现在由于没有类似KMP的border的单调性，我们必须用主席树维护了。注意实现的时候，每次失配时一定要顺着fail链走上去而不是直接将转移置为fail节点的对应转移，否则会由于字符集太大无法保证复杂度（注意如果是一棵普通的trie而且字符集很小，一定要将转移置为fail节点的对应转移，因为普通trie的叶子节点深度之和可能很大）。

接着将原串在AC自动机上走一遍，最后更新子树和。注意如果暴力更新子树和会由于复杂度不对而超时。

注意要用平衡树或者hash存储转移。

时间复杂度$O(n(\log n+\log q)+\sum m_i\log m_i)$。（$q$是因为AC自动机上每个点度数最多是$q$）

算法四

注意到如果$max{m}_i\le 25$，我们可以对于长度小于$max{m}_i$的串全部预处理一遍hash值并存下来，具体来说可以存在一个数组里面然后排序，然后询问的时候直接二分查询个数即可。

用树状数组加上异或哈希实现常数较小，可以通过四个$max{m}_i\le 25$的点。

时间复杂度$O(nmax{m}_i\log n+q\log (nmax{m}_i))$。

算法五

我们考虑在线怎么做。对于普通的字符串，这个问题显然是用后缀三兄弟或后缀平衡树解决。那么在这个问题上是不是也可以如此呢？

后缀数组！

慢着……这玩意儿。。。后缀数组要求把后缀进行排序，很好，两个名次数组怎么比较顺序？

后缀自动机！

慢着……这玩意儿。。。一个结点能识别的子串的长度都不固定，怎么玩？

后缀平衡树！

慢着……这玩意儿。。。还是不知怎么比较两个名次数组的顺序啊。

后缀树！

慢着……这玩意儿。。。诶不慢，好像可以。

考虑用Ukkonen算法构造后缀树的过程，显然每一步也很容易用主席树推广到这题上。

然而直接用 Ukkonen 算法会被卡复杂度。我们把孩子数不等于 $1$ 的非根节点称为特殊节点，原因是在普通串上，一个特殊节点的后缀链接显然会指向一个特殊节点，因为特殊节点已经有两个不同的字母作为转移，那么它的后缀链接肯定也有这两种字母，而在本题中不然，由于后缀链接指向了一个更浅的点，因此两种转移可能会合并为一个。

解决方法很简单，在找后缀链接的时候，如果它的父亲不是特殊节点，那就找它父亲的父亲，直到找到一个特殊节点，再从那个特殊节点开始求出当前点的后缀链接，可以证明这样的复杂度是正确的。

构造完后缀树之后求一遍子树和，每次在后缀树上跑一边查询即可。

时间复杂度 $O(n\log n+\sum m_i(\log m_i+\log n))$。

有人说，有后缀数组和后缀自动机了，还要后缀树干嘛？从这题可以看出，每个数据结构都有自己的特性。后缀树在这题上能够成功的原因，也许是因为他其实是某种后缀 Trie 的 AC 自动机吧。而 AC 自动机能够解决离线问题的原因，也许是因为他其实是推广后的 KMP 吧。这一切，也许正是奥林匹克数据结构的魅力所在。