Arena
设 \(f_{i,j}\) 表示当前考虑 \(i\) 个英雄，这 \(i\) 个英雄初始血量最大值为 \(j\) 的方案数。
显然第一轮中，每个英雄血量都会减少 \(i-1\)：
- 若 \(i-1\ge j\)，所有英雄都会在第一轮死亡，显然合法，方案数为 \(j^i-(j-1)^i\)；
- 否则，考虑枚举这一轮后存活的英雄数量 \(k\)，这 \(k\) 个英雄剩余血量一定是 \(j-(i-1)\)，而死去的 \(i-k\) 个英雄的血量可以在 \([1,i-1]\) 中随意选取，总方案数为\[\sum_{k=2}^i\binom{i}{k}f_{k,j-(i-1)}\times (i-1)^{i-k} \]
时间复杂度 \(O(n^2x)\)。
[NOIP2024] 遗失的赋值
首先判一元限制冲突的情况。
考虑 \(n-1\) 个二元关系：
- 若 \(i\) 和 \(i+1\) 位置都存在一元限制，方案数为 \(v\times (v-1)+1\)；
- 否则，考虑将一元限制排序：
第 \(i\) 个和第 \(i+1\) 个一元限制之间有 \(c_{i+1}-c_i\) 组二元限制，若不设任何限制有 \(v^{2l}\) 种方案，其中不合法的方案一定是从 \(c_i\) 一直限制到 \(c_{i+1}\)，总共 \(v^{l-1}\times (v-1)\) 种。
全部乘起来即可。
分割（divide）
容易发现，一组合法方案的 \(d\) 一定都相同。所以考虑按深度计算，设当前考虑深度 \(dep\)。
设 \(maxdep_u\) 为 \(u\) 子树中深度最大的节点的深度，将同层的节点的 \(maxdep\) 排序，设当前考虑的 \(maxdep\) 为 \(b\)，大于 \(b\) 的同层节点有 \(sum\) 个，同层中 \(maxdep=b\) 的节点为 \(c_b\) 个，钦定 \(d_1\) 为 \(maxdep=b\) 的节点，则方案数为 \(c_b\times(A_{c_b+sum-1}^{k-1}-A_{sum}^{k-1})\)（因为除 \(d_1\) 所对的节点外至少要再选 \(1\) 个 \(maxdep=b\) 的才能满足限制），特别地，\(c_b=k-1\) 时，可以令包含根节点的连通块满足限制，就不需要减 \(A_{sum}^{k-1}\) 了。
时间复杂度 \(O(n\log n)\)。