====== 结论 2 ======

===== 1、点对最远距离 =====

给定 $n$ 个数，要求将 $n$ 个数进行排列，使得所有数值相同的点对的距离的最小值尽量大。

答案为 $\lfloor \cfrac {n-\text{cnt}}{\text{maxfreq}}\rfloor$，其中 $\text{maxfreq}$ 为相同数值的数出现的最大频率，$\text{cnt}$ 为出现频率为 $\text{maxfreq}$ 的数值的个数。

假设出现频率为 $\text{maxfreq}$ 的数为 $a,b,c$。

考虑这样放置：$a,b,c,....a,b,c,....a,b,c,\ldots a,b,c$

接下来对剩余的数按出现频率排序后，按数字标注顺序依次放置即可: $a,b,c,1,4,7,10,a,b,c,2,5,8,11,a,b,c,3,6,9,a,b,c$

===== 2、树同构 =====

给定一棵无根树，任选一个结点添加一个新结点能得到的所有不同构的树的个数等于以原树的每个结点为根的不同构的有根树个数。

===== 3、球盒问题 =====

将 $n$ 个球放入 $m$ 个盒子中，允许有空盒，球和盒子都没有区别，问方法数。

该问题等价于:

  - $a_1\le a_2\le \cdots \le a_n$
  - $a_1+a_2+\cdots a_n=m$

考虑将上述操作分解为若干次操作，第 $i$ 次操作选择 $a_1\sim a_i$ 并都加上 $j$，则第 $i$ 次操作对应的生成函数为

$$\sum_{j=0}^{\infty} x^{ij}=\frac 1{1-x^i}$$

于是总方法数为

$$[x^n]\prod_{i=1}^m \frac 1{1-x^i}$$

但发现上式难以计算，考虑 $\text{dp}$ 计算答案。设  $\text{dp}(i,j)$ 表示将 $i$ 个球放入 $j$ 个盒子中的方法数。

假如至少有一个盒子是空的，则删去一个盒子也不影响方法数，于是 $\text{dp}(i,j)\gets \text{dp}(i,j-1)$。

如果所有盒子至少有一个球，则可以与每个盒子去掉一个球的方案构成一一映射，于是 $\text{dp}(i,j)\gets \text{dp}(i-j,j)$。

于是可以 $O(nm)$ 得到答案。

===== 4、字符串变化 =====

给定串 $s_1,s_2$，保证 $s_1,s_2$ 中每种字符数量相同。每次允许交换 $s_1$ 中相邻的两个字符，问至少需要经过多少次操作才能得到 $s_2$。

假设有两个相邻的相同字母，则不应该交换这两个字符。于是交换过程中 $s_1$ 中同种字符的相对顺序不应该改变。

于是对同一种字符，$s_1$ 中的每个字符的最终位置应该按顺序与该字符在 $s_2$ 中的位置一一对应。

于是可以求出 $s_1$ 中所有字符在 $s_2$ 中的最终位置，然后接下来的操作等效于冒泡排序，于是操作数等于逆序对数。

===== 5、二进制表示 =====

假定有 $a_i\gt 0$ 个 $2^i(0\le i\le n)$，则可以表示出 $\sum_{i=0}^n a_i2^i$ 内的所有数。

===== 6、石子游戏 =====

以下两个条件等价：

  - 每次可以拿 $S=\{a_1,a_2\cdots a_k\}$ 个石头的游戏等价于每次可以拿 $[\min S,\max S]$ 个石头的游戏。
  - 对任意 $a_i,a_j\in S$，若 $a_i+\min S\lt a_j$，则存在 $a_k\in S$，使得 $a_i\lt a_k\lt a_j$。

详细见 [[https://wiki.buaaacm.com/doku.php?id=2020-2021:teams:legal_string:jxm2001:contest:cf_feb21#multiple_games|证明]]

===== 7、线性表示 =====

当 $a,b$ 互素时，$ax+by(x,y\ge 0)$ 不能表示的正数等价于所有形如 $ab-an-bm(n,m\ge 1)$ 的正数。

一方面，考虑 $ab-a-b=a(b-1)-b=b(a-1)-a$ 显然不能表示为 $ax+by(x,y\ge 0)$。

当 $k$ 不能表示为 $ax+by(x,y\ge 0)$ 时，显然 $k-a,k-b$ 均不能表示为 $ax+by(x,y\ge 0)$。

于是所有形如 $ab-an-bm(n,m\ge 1)$ 的正数均不能表示为 $ax+by(x,y\ge 0)$。

另一方面，考虑任意 $ax+by(x,y\ge 0)$ 不能表示的正数，这个数一定表示为 $ax'+by'$，调整 $x'$ 使得 $0\le x'\lt b$，于是有 $y'\lt 0$。

于是有 $ax'+by'=ab+a(x'-b)+by'$，令 $n=b-x',m=-y'$，于是有 $n,m\ge 1$。

故任意 $ax+by(x,y\ge 0)$ 不能表示的正数一定可以表示为 $ab-an-bm(n,m\ge 1)$。证毕。