题目大意

  一个置换可以看成是有 $a_1$ 个长度为 $1$ 的环 + $a_2$ 个长度为 $2$ 的环 + …… + $a_n$ 个长度为 $n$ 的环，满足 $\sum_{i=1}^n i\cdot a_i=n$ 。
  记 $f(a_1,a_2,\cdots,a_n)$ 表示各种环的数量分别为 $a_1,\cdots,a_n$、长度为 $n$ 的置换的数量，现给定 $n,p$（$p$ 是质数），问有多少种不同的数列 $a_1,\cdots,a_n$，满足 $p \not|\ f(a_1,a_2,\cdots,a_n)$ 。

  $n \leq 10^{18},\ \ 2 \leq p \leq 10^5$
  多测，$T \leq 10^5$，2s

题目大意

  记 $f(n)$ 表示 $\sum_{d|n,\ \gcd(n,\frac nd)=1}d$，给定 $n$，求 $\sum_{i=1}^n f(i) \bmod 10^9+7$。

  $n \le 10^{12}$
  多测，10 组数据，20s，32768K 。

题目大意

  给定一个 $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