F-東京ワッショイ 题解

想组乐队的加我（bushi 以及打个广告： 对hut立直麻将协会与音游群感兴趣的可以找我了解（

瞪眼法

按照不同策略多分几次，可以发现每次得分都是相同的

于是可以大胆推断得分与如何分无关，是一个固定值

我们贪心地拆，每次只拆出一个作为一堆，发现结果为$(n-1)\times1+\cdots +1\times 1=\frac{n(n-1)}{2}$

于是可以直接对每个输入直接进行计算输出

注意$10^9$的数据会超过int类型的限制，需要定义数据类型为long long

标答

根据以上假设，我们使用数学归纳法。令

$P(n)$ 为命题：“所有将 $n$ 个拨片分开的方式所得分数均为

$$\frac{n(n-1)}{2}.$$

基础情况

如果 $n=1$，则只有一个拨片，无可移动，游戏的总得分为

$$\frac{1\cdot(1-1)}{2}=0.$$

因此 $P(1)$ 成立。

推导步骤

现在我们要证明：对任意 $n\ge1$，若 $P(1),\dots,P(n)$ 均为真，则 $P(n+1)$ 也为真。

• 假设 $P(1),\dots,P(n)$ 均成立，现有一堆大小为 $n+1$ 的拨片。
• 首次拆分必将此堆分为两堆，大小分别为 $x$ 和 $y$，满足$$x>0,\quad y>0,\quad x+y=n+1.$$
• 总得分可分为三部分：
  1. 第一次拆分得分：$x\times y$；
  2. 拆分大小为 $x$ 的子堆所得得分：$\frac{x(x-1)}{2}$（由 $P(x)$）；
  3. 拆分大小为 $y$ 的子堆所得得分：$\frac{y(y-1)}{2}$（由 $P(y)$）。

故总得分为

$$\begin{aligned} \text{总得分} &= \text{(第一次移动的得分)}\\ &\quad + \text{(分出x个拨片的得分)}\\ &\quad + \text{(分出y个拨片的得分)}\\ &= xy + \frac{x(x-1)}{2} + \frac{y(y-1)}{2} &&\text{by }P(x)\text{ and }P(y)\\ &= \frac{2xy + x^2 - x + y^2 - y}{2}\\ &= \frac{(x + y)^2 - (x + y)}{2}\\ &= \frac{(x + y)(x + y - 1)}{2}\\ &= \frac{(n+1)n}{2}. \end{aligned} $$

这正是 $P(n+1)$ 所要求的。
因此由数学归纳法，$P(1),P(2),\dots,P(n)$ 蕴含 $P(n+1)$，命题得证。■