UOJ Round #15
A. 奥林匹克五子棋
30
$2 \le n, m \le 4$
暴力枚举所有局面判断是否合法。
时间复杂度 $\mathcal O(2^{n m} n m)$。
45
$\min(n, m) = 1$。
若对于 $n, m, k$ 有解，则对于 $n, m, k + 1$ 有解。
$k = 1$ 时无解。
$k = 2$ 时双方棋子间隔分布即为可行解。
$k \gt 2$ 同理。
时间复杂度 $\mathcal O(n m)$。
60
$n, m \ge 2, \min(n, m) \lt k$
斜线方向明显符合条件，像黑白染色那样，横竖方向最长连续段均为 $1$。
时间复杂度 $\mathcal O(n m)$。
100
$n, m \ge 2$
$k = 2$ 时无解。
$k = 3$ 时一定不会出现 $2 \times 2$ 的同色块，进而同色的 L 形也不能存在，这样一来构造必须是 $1 \times 2$ 间隔分布。
$k \gt 3$ 同理。
时间复杂度 $\mathcal O(n m)$。
B. 奥林匹克环城马拉松
20
$n \le 6, t_i \le 4$
存在一个点度数为奇数时方案数为 $0$。
从 $1$ 号点开始搜索欧拉回路，记录当前在哪和任意两点之间未走边数，状态数为 $\prod t_i \times n$。
每次枚举下一步往哪走，可以从将要走的路上选一条未走过的边来走，并乘以这条路上剩余的边数，转移复杂度是 $\mathcal O(n)$。
40
$m = n - 1$
树。
看题解。
70
如果去掉重复道路，则道路的连接形成了一个环
环。
有向图的欧拉回路计数问题通用公式：
\[T \cdot \prod (deg_x - 1)!\]其中 $T$ 是以某个节点为根的树形图数目。
问题转化为给图定向。
枚举在环上转了几圈，那么每条边往两个方向走的次数都能计算出来。
问题转化为求环的树形图数目。
枚举断开的边转化成树的形式。
时间复杂度 $\mathcal O(n \max t_i)$。
100
$1 \le n - 1 \le m \le n \le 1000$
$1 \le t_i \le 4000$
环套树。
枚举任意一条环边正着走了多少次，根据有向图欧拉序列条件式 $indegree_x = outdegree_x$ 就可以直接给无向边定向，定向的方案数直接用组合数计算就好了，例如 $t_i$ 条无向边有一侧是 $s_i$ 条，方案数就是 $\prod \binom{s_i}{t_i}$。
第二步是树形图计数，这一步只要把环上的树形图计数和每个点的外向树树形图计数直接乘起来即可。
最后乘以 $\prod (deg_x-1)!$ 即可。
时间复杂度 $\mathcal O(n \max t_i)$。
C. 奥林匹克数据结构
20
$n \le 2000$
$q \le 50$
$\sum m_i\le 10000$
按照题意模拟。
时间复杂度 $\mathcal O(n \sum m_i)$。