Atcoder Soundhound2018_summer_qual_c Ordinary Beauty题解

让我们将序列 \(a\) 的「美」定义为绝对差为 \(d\) 的两个相邻元素对的对数。
总共有 \(n^m\) 个长度为 \(m\) 的序列，其中每个元素都是 \(1\) 到 \(n\) 之间的整数。求每个序列的「美」的平均值。

数学题。

以 \(\{2,3,1\}\) 为例，\(8\) 个序列分别是 \(\{1,1,1\},\{1,1,2\},\{1,2,1\},\{1,2,2\},\{2,1,1\},\{2,1,2\},\{2,2,1\},\{2,2,2\}\) 。
他们的「美」分别是 \(0,1,2,1,1,2,1,0\) ，平均值是 \(1\) 。

我们发现，平均值只与所有序列中相邻两个数的差有关。两个数差值小于 \(d\) 则「美」加一，否则没有贡献。
那么问题就转化为统计序列中两个数差值小于 \(d\) 的对数。
因为我所有序列都有了，所以，相邻两个数一定等概率出现，就是说， \(1,2\) 和 \(2,1\) 和其他各种数对出现的次数是一样的。
那么用概率学知识知道，这是一个古典概型。等可能性数是 \(m^2\) ，而两个数差值小于 \(d\) 的对数分两类。若 \(d=0\) ，则可能性数是 \(n\) ，否则找一些规律可以知道是 \(2\times (n-d)\) 。一个数列中共有 \(m-1\) 对相邻数，所以分子还要再乘上 \(m-1\) 。那么答案就出来了。

\[Ans=\begin{cases} \frac{m\times n}{n^2}=\frac{m}{n}, & d=0\\ \frac{m\times (2\times(n+d))}{n^2}, & d \neq 0 \end{cases} \]

做完了，没必要贴代码。