题目大意

  给定一个 $n$，表示一棵有标号无根树有 $n$ 个结点。
  有如下限制：

1. 给定 $m$ 个数对 $(x_i,y_i)$，表示树上一定要有 $(x_i,y_i)$ 这条边；
2. 有 $k$ 个限制 $op_i\ x_i\ deg_i$，若 $op_i=0$ 表示 $x$ 的度数至少为 $deg_i$，若 $op_i=1$ 表示 $x$ 的度数至多为 $deg_i$。

  求合法的树的数量。

  $2 \leq n \leq 60,\ 0 \leq m \leq n-1,\ 0 \leq k \leq 60$
  1s

传说中的，鸭大计科鬼门关

题目大意

  对于一个序列 $a_1,\cdots,a_n$，Alice 和 Bob 在上面博弈，Alice 先手，两人轮流操作，每人每次要么拿走第一个元素或者最后一个元素，谁先使得这个序列不增或不降就获胜（如果一开始就不增或不降那么 Bob 获胜）。
  现在给定一个序列 $a_1,\cdots,a_n$，有 $Q$ 个询问，每次询问给出 $l,r$，问 $a_l,a_{l+1},\cdots,a_r$ 的博弈结果。

  $n,Q \leq 10^6,\ \ a_i \leq 10^9$
  3s

题目大意

  有一个池塘，中间有 $n$ 行 $n+1$ 列的石头阵。
  连边只能连相邻的格子，相邻定义为四连通。
  现在左边第一列石头已经跟左边大陆 $L$ 相连，右边最后一列石头已经跟右边大陆 $R$ 相连。问剩下的有多少种连边方式，使得 $L$ 与 $R$ 连通。

  $n \leq 42$

题目大意

  定义函数 $f(n)$ 表示对 $n$ 一直求数位和直至 $n$ 为个位数，即：

  其中 $g(n)$ 表示 $n$ 的数位和。
  现在有一个很大的 $n$，你要求 $f(n)$。
  这个 $n$ 是根据四个参数 $a,b,m,k$ 生成的，首先生成 $k$ 个数 $a,a+b,a+2b,\cdots,a+(k-1)b$（都在 $\bmod~m$ 意义下），然后把它们从后往前拼起来，就是 $n$。比如，$a=42,b=42,m=2018,k=18$，会生成 $n=7567146726305885465044624203783362942522101681268442$。

  $0 \leq a,b \leq 10^9,\ 2 \leq m \leq 10^9+7,\ 1 \leq k \leq 10^9$
  多测，$T \leq 10^4$

题目大意

  给定一个长度为 $n$ 的序列 $a_1,\cdots,a_n$，求所有区间的 $mex$ 平均值之和，即

  $1 \leq n \leq 5 \times 10^5,\ \ 0 \leq a_i \leq 5 \times 10^5$

题目大意

  给定一个 $n \times m$ 的 01 矩阵 $A_0$。定义一次操作为将这个矩形每个元素求异或前缀和，即 $A_k[i,j]=(\sum_{u=1}^i\sum_{v=1}^j A_{k-1}[u,v]) \bmod 2$。
  求一个最小的正整数 $k$，使得 $A_0=A_k$。

  $n\times m \leq 10^6$

题目大意

  给定一个长度为 $n$ 的排列。
  现在有两个空数组 $X$ 和 $Y$，你要依次把排列的每个元素放到 $X$ 数组或者 $Y$ 数组，使得最后 $X$ 数组和 $Y$ 数组的 high element 个数相同。定义数组中一个元素为 high element 当且仅当它是其前缀最大值。
  一个元素放 $X$ 数组记为 $0$，放 $Y$ 数组记为 $1$，你要求字典序最小的方案，或输出无解。

  $n \leq 2 \times 10^5$

  正儿八经的用析合树本身的题没见着，析合树形态计数倒是一大堆。。。

题目大意

  给定一棵 $n$ 个点的 AVL 树（点权恰好为 $1$ 到 $n$），你需要选择其中的 $k$ 个点，满足：

1. 如果要选一个点，那么它的祖先也必须选。也就是选出来的 $k$ 个点会组成一棵新的树。
2. 这棵新的树也必须是 AVL 树。

  （放个传送门里面有图片可以看看例子

  每种选法可以表示为一个长度为 $n$ 的 01 串（表示每个点选或不选），你需要求出字典序最大的方案。

  $1 \leq k \leq n \leq 5 \times 10^5$
  4s，256MB

题目大意

  有 $k$ 棵树，每棵树有 $n$ 个点，对于所有的点对 $(s,t)$（$1 \leq s,t \leq n$），求出有多少个点在每棵树的 $s$ 到 $t$ 的链上都存在。
  （以防表述不清，给一下传送门
  $n,k \leq 500$
  2s

题目大意

  给定 $L,R$，求从 $L$ 到 $R$ 的这 $R-L+1$ 个数中能选出多少个不同的子集，满足子集中所有的数的乘积是一个完全平方数。特别地，空集也算一种选法，定义其乘积为 $1$。

  多测，$T \leq 100$
  $1 \leq L \leq R \leq 10^7,\ \ \sum_{i=1}^T R_i-L_i+1 \leq 6 \times 10^7$
  5s

题目大意

  维护三个长度为 $n$ 的序列 $A,B,C$，支持以下 7 种操作：（操作数为 $m$）

• $1\ l\ r$：对 $[l,r]$，$A_i \gets A_i+B_i$；
• $2\ l\ r$：对 $[l,r]$，$B_i \gets B_i+C_i$；
• $3\ l\ r$：对 $[l,r]$，$C_i \gets C_i+A_i$；
• $4\ l\ r\ v$：对 $[l,r]$，$A_i \gets A_i+v$；
• $5\ l\ r\ v$：对 $[l,r]$，$B_i \gets B_i \cdot v$；
• $6\ l\ r\ v$：对 $[l,r]$，$C_i \gets v$；
• $7\ l\ r$：求 $\sum_{i=l}^r A_i,\ \sum_{i=l}^r B_i,\ \sum_{i=l}^r C_i$，在模 $998244353$ 意义下。

  $n,m \leq 2.5 \times 10^5,\ 0 \leq A_i,B_i,C_i < 998244353$
  5s

题目大意

  有一幅 $n$ 个点 $m$ 条边的简单带权无向图，对于每个点 $i$，你要求出一棵生成树，满足：

1. 与 $i$ 相连的边全部在这棵生成树中；
2. 生成树边权和最小。

  $n \leq 10^5,~m \leq 3 \times 10^5,~边权w_i \leq 10^9$
  5s

由来

  2019 年南京 Regional 充分暴露了这个问题，市面上大多数标着 $O(n^3)$ 的 KM 板子实际上是 $O(n^4)$ 的，以致选手如果是用了经典书籍上的板子，或者是网上随便扒的板子，就会 TLE。
  然后最近做题做到了 KM，就想补一个自己的真·$O(n^3)$ 的 KM。网上的 $O(n^3)$ 也都没有教程只能自己啃代码，就想把思路写一下。
  大二了才会 KM 你丢不丢人