A. [The 2023 ICPC Asia Macau Regional Contest] Random Tree Parking

给定一棵随机生成 ($fa(u)$ 在 $[1,u-1]$ 中随机生成) 树, 求满足以下条件的长为 $n$ 的序列 $A$ 的个数: 对树染色, 初始为白, 按顺序 $i=1\sim n$, 在 $A_i$ 中的祖先中找到最深的白色点, 染黑, 不能找不到. $n\le 10^5$.

$F(u,i)$ 表示在以 $u$ 为根的子树中, 要染黑祖先中 $i$ 个点的方案数. 初始 $F(u)=[1,1,\cdots]$, 转移: $F'(u,i-1)\gets \sum_j F(u,j-1)F(v,i-j)\frac{(i+siz(u)+j+siz(v))!}{(i+siz(u))!(j+siz(v))!}$. 用该方式随机的树, 树高为 $O(\log n)$ 的, 故时间复杂度 $O(n\log^2 n)$.

B. [The 2023 ICPC Asia East Continent Final Contest] Equal Sums

给定 $n$ 个区间 $[L^1_i,R^1_i]$, $m$ 个区间 $[L^2_i,R^2_i]$, 对于每个 $p\le n,q\le m$, 求满足条件序列 $X,Y$ 的个数: $|X|=p,|Y|=q$, $X_i\in [L^1_i,R^1_i],Y_i\in [L^2_i,R^2_i]$, $\sum_i X_i=\sum_i Y_i$. $n\le 500$, 值域 $500$.

考虑 DP: $F(i,j,x)$ 表示 $X$ 中前 $i$ 个, $Y$ 中前 $j$ 个, $\sum X([1,i])-\sum Y([1,j])$ 为 $x$ 的方案数. 但这样值域为 $O(n^2)$ 的. 考虑当 $x\le 0$ 时加入 $X_{i+1}$, 否则加入 $Y_{j+1}$, 这样值域就是 $O(n)$ 的. 时间复杂度 $O(n^3)$.

C. [ATCoder Tupc 2023] And DNA

给定 $n,m$, 求长为 $n$ , 值域为 $[1,m]$ 的环状序列 $A$ 满足 $\forall i,A_i+(A_{i-1}\text{ bitand }A_{i+1})=m$. $n,m\le 10^9$.

$m=0$ 是简单的. 当 $m=1$ 时, 考虑 DP: $F(i,a,b)$ 表示考虑到第 $i$ 位, $A_i=a,A_{i-1}=b$ 的方案数, 矩阵优化 (设 $B$ 表示转移矩阵, 答案即为 $\sum_i B^n_{i,i}$). 当 $m$ 为奇数时, 发现只考虑 $A_i$ 和 $m$ 的最低位为 $m=1$ 的情况, 且不进位. 当 $m$ 为偶数时, 要不所有 $A_i$ 的最低位均为 $0$, 为 $m/2$ 的情况, 要不所有 $A_i$ 最低为均为 $1$, 产生进位, 为 $m/2-1$ 的情况.

时间复杂度 $O(\log n)$.