一些结论

· · 算法·理论

From CF Kar Salesman

对于 n 个数的序列 a，每次对于 m 个数减 1，最多需要 max(max\{a_i\},\lceil \sum a_i/m \rceil)

From [20241015] 洗牌

你有 n 张牌，按顺序依次是 a_1,a_2,...,a_n 为大小为 n 的排列。可执行以下操作：

1.把第一张放到最后去。

2.当牌顶的牌是最小的牌时，拿走当牌顶牌。

问：拿走所有牌所用最小操作一的次数。

进一步转化，将操作一变为一个指针的移动，操作二的拿走看做跳过当前牌。问题就转化为了以 1,2,...,n 的顺序遍历序列，问行走步数。

第i步需要从权值为i的位置移动到权值为i+1的位置，设代价为 g_i。

有：

g_i=dis(i,i+1),p_i<p_{i+1} =m-i-dis(i,i+1),p_i>p_{i+1}

化简有：

g_i=p_{i+1}-p_i,p_i<p_{i+1} =m-i-p_i+p_{i+1},p_i>p_{i+1}

(加不加1的细节没仔细考虑，大概是这样，p_i表示权值为i的位置，注意p_i此时应为动态的)

答案为 \sum_{i=1}^{n-1}g_i 。然后你会发现有关p_i的项可以消。对于相邻的两项，当 p_i<p_{i+1} 的时候，下一轮的 p_{i+1} 会 -1，但这个影响为常量。所以化简后的式子与 p_i 是没有关系的。

具体地，答案为：

\sum_{i=1}^{n-1}(m-i)[p_i>p_{i+1}]

给定每个数的儿子个数，求合法的又根树的个数。

将问题转化为有多少个合法的 father 数组集。容易发现，肯定有 f_i\neq i，且对于 u ,r_u（ u 的儿子个数）即为 u 在数组中出现的位置。

按顺序去考虑每一个 u ，发现有 f_u 被占和不被占的情况。当 f_u 不被占的时候，就是在剩余的位置中放 r_u 个 u ，设 s_i=\sum_{j=1}^i r_j，则当前方案为 C_{n-s_{u-1}-1}^{r_u} ，减1的原因是 u 不能做自己的父亲。当 f_u 被占的情况，剩余的位置有 n-s_{u-1} 个数，直观上讲它是可以取这里面的任意位置的。但是如果真是这样就不可高效完成，而且确实是有问题的。f_u 有值的时候，说明 u 已经加入树内，则 u 的最高祖先的 father 值也是空的，但显然是不能作为 u 的儿子的，所以方案也是 C_{n-s_{u-1}-1}^{r_u}。

所以方案数就是：

\sum_{i=1}^nC_{n-s_i-1}^{r_i}

经过简单的代还会发现就是：

\frac{(n-1)!}{\prod_{i=1}^nr_i!}

From [20241109] 锦标赛

对于线段树的一次建树过程，每次合并的操作为枚举左边和右边时，时间复杂度为 O(n^2) 。

From [Ynoi Easy Round 2021] TEST_152

对于n个不同颜色的段覆盖，最后分的的区间段最多 O(n)。

From 消除游戏

对于分为两边分别为 n、m 个点的二分图，生成树有 n^{m-1}m^{n-1} 种。

From [20250701]BST

所有点的深度和等于所有点的子树和。

From 团队选拔

固定一个端点的区间不同的 gcd 只有 log 种，故对于一个长度为 n 序列，所有区间的不同的 gcd 共有nlogV 种。

upd20250916：注意到，有同样性质的还有或和与。

From [20250909]快速kmp

一个序列的最大周期数等于其字符集中两两构成的子序列的最大周期数的最小公倍数，如此还能求出原序列的最小周期长度。

From 2025 CSP-S 模拟赛 Day 16 C. 连通块

prufer 序推论，设目前有 m 个连通块，大小分别为 a_1,a_2,……,a_m，则在连通块之间连边最后形成一棵树的方案数为 \Pi^m_{i=1}a_i(\sum^m_{i=1}a_i)^{m−2} 。

From [20251028] 树锯解构

同理于 min-max 容斥，与和或通过异或也能够同样转换。

From AGC006C

将 a_i 变成 a_{i-1}+a_{i+1}-a_i ，相当于交换相邻两位的差分。