Attention Is All You Need?

C 数列之和

• 数列 $a$ 由 $10^{100}$ 项组成，从第一项开始有 $a_i = 2i - 2$。
• 将数列 $a$ 中所有长度大于 $1$ 的连续子数列的元素和去重后从小到大构成一个新的数列，求这个数列的第 $k$ 项。

注意到，答案为 $2(k + \lfloor \log_2{(k + \lfloor \log_2 k \rfloor)} \rfloor)$，时间复杂度 $\mathcal O(T)$。

#include <bits/stdc++.h>
using namespace std;
int T;
long long k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> k;
        cout << 2 * (k + __lg(k + __lg(k))) << '\n';
    }
    return 0;
}

证明

不妨设 $b_i = i - 1$（$i \le 10^{100}$），即数列 ${0, 1, 2, \cdots, 10^{100} - 1}$，最后再乘 $2$ 即可。

由于 $10^{100} \gg \max {k} = 10^{18}$，因此完全可以视为是无穷数列。

接着考虑什么样的数能够由数列 $b$ 中长度大于 $1$ 的连续子数列的元素和表示出来。

注意到，满足这样条件的正整数 $n$ 是比较特殊的，即存在一个正奇数 $p$ 和一个正整数 $q$，使得 $n = pq$。经过讨论，我们发现这类数总能被表示出来：

1. 当 $q \ge \frac{p-1}{2}$ 时，构造以 $q$ 为中间元素、长度为 $p$ 的连续子数列，即包含 $q - \frac{p-1}{2} \sim q + \frac{p-1}{2}$ 内的所有整数。

2. 当 $q \le \frac{p+1}{2}$ 时，构造以 $\frac{p-1}{2}$、$\frac{p+1}{2}$ 为中间元素、长度为 $2q$ 的连续子数列，即包含 $\frac{p+1}{2} - q \sim \frac{p-1}{2} + q$ 内的所有整数。

当 $q \in {\frac{p-1}{2}, \frac{p+1}{2}}$ 时，这两种构造方式均有效，如 $n = 3, p = 3, q = 1$ 时，有 ${0, 1, 2}$ 和 ${1, 2}$ 两种构造方式。

进一步地，不难发现上述讨论实际上已经囊括了所有长度大于 $1$ 的连续子数列：

1. 当子数列长度 $l$ 为奇数时，令 $p = l$，首项取遍 $\mathbf N$，则中间元素取遍大于等于 $\frac{p-1}{2}$ 的所有整数。令 $q$ 为中间元素，则 $q$ 取遍大于等于 $\frac{p-1}{2}$ 的所有整数，此时恰与前述的情形 1 对应。

2. 当子数列长度 $l$ 为偶数时，令 $2q = l$，首项取遍 $\mathbf N$，则两个中间元素分别取遍大于等于 $q-1$ 和大于等于 $q$ 的所有整数。令 $\frac{p-1}{2}$、$\frac{p+1}{2}$ 为中间元素，则 $q$ 取遍小于等于 $\frac{p+1}{2}$ 的所有整数，此时恰与前述的情形 2 对应。

因此，对于一个整数 $n$，当且仅当存在一个正奇数 $p$ 和一个正整数 $q$ 使得 $n = pq$ 时，$n$ 能够被数列 $b$ 中长度大于 $1$ 的连续子数列的元素和表示出来。

显然，这个条件又等价于 $n \neq 2^k$（$k$ 为正整数），因为只有 $2$ 的正整数次幂没有奇因子。也就是说，答案数列为 ${0, 1, 3, 5, 6, 7, 9, \cdots }$（A138591）。

最后乘 $2$ 即为本题答案。

---

J 铁刀磨成针

一把刀的初始攻击力为 $x$。现进行 $n$ 个回合，每回合依次包含下面两个阶段：

• 磨刀阶段：若磨刀石有剩余，可选择消耗 $1$ 个磨刀石使刀的攻击力提升 $1$。
• 攻击阶段：若刀的攻击力大于 $0$，可选择进行一次攻击，造成的伤害等于攻击力，随后刀的攻击力减 $1$。当刀的攻击力为 $0$ 时，刀损坏，此后不能再攻击。

注意到，答案为

$$
ans(n, x, y) =
\begin{cases}
n’(x + 1) & n’ \le \min(x + 2, y) \cr
\lfloor \frac{(n’+x+1)^2}{4} \rfloor - \frac{(n’-y)(n’-y+1)}{2} & n’ \ge \max(x + 2, y) \cr
\lfloor \frac{(n’+x+1)^2}{4} \rfloor & x + 2 \lt n’ \lt y \cr
n’(x+1) - \frac{(n’-y)(n’-y+1)}{2} & y \lt n’ \lt x + 2
\end{cases}
$$

（其中 $n’ = \min(n, x + 2y - 1)$）

时间复杂度 $\mathcal O(T)$。

#include <bits/stdc++.h>
using namespace std;
int T, n, x, y;
int solve(int n, int x, int y) {
    if (n <= min(x + 2, y)) return n * (x + 1);
    if (n >= max(x + 2, y)) return (n + x + 1) * (n + x + 1) / 4 - (n - y) * (n - y + 1) / 2;
    if (n > x + 2 && n < y) return (n + x + 1) * (n + x + 1) / 4;
    if (n > y && n < x + 2) return n * (x + 1) - (n - y) * (n - y + 1) / 2;
    assert(false);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    while (T--) {
        cin >> n >> x >> y;
        n = min(n, x + 2 * y - 1);
        cout << solve(n, x, y) << '\n';
    }
    return 0;
}

考场做法（如何注意到？）

相比于 C 题，这道题有三个参数，需要的注意力比较高。因此只能退而求其次，先打个暴力。

设 $dp_{i,j}$ 表示在第 $i$ 轮的攻击力为 $j$ 的情况下，前 $i$ 轮造成的总伤害。不难发现，先用磨刀石总优于后用磨刀石，因此可得转移方程：

0. 初始状态：$dp_{0,x} = 0$

1. 磨刀且攻击，伤害仍为 $j$（要求有磨刀石剩余，即 $i \lt y$）：

$$dp_{i+1,j} = \max(dp_{i+1,j}, dp_{i,j} + j + 1)$$

2. 磨刀且不攻击，伤害变为 $j + 1$（要求有磨刀石剩余，即 $i \lt y$）：

$$dp_{i+1,j+1} = \max(dp_{i+1,j+1}, dp_{i,j})$$

3. 不磨刀且攻击，伤害变为 $j - 1$（要求刀不损坏，即 $j \gt 0$）：

$$dp_{i+1,j-1} = \max(dp_{i+1,j-1}, dp_{i,j} + j)$$

4. 不磨刀且不攻击，伤害仍为 $j$（对 $i, j$ 无限制）：

$$dp_{i+1,j} = \max(dp_{i+1,j}, dp_{i,j})$$

注意到，只有前 $x + 2y - 1$ 轮才是有意义的。有石必磨刀总是更优，有效轮数最多的情况是先耗完所有磨刀石（$y$ 轮）再攻击（$x + y$ 轮），但最后一次磨刀和第一次攻击可以合并，需减 $1$。因此，我们可以直接上来就让 $n$ 变成 $\min(n, x + 2y - 1)$。

long long solve(int n, int x, int y) {
    memset(dp, 0x80, sizeof(dp));
    n = min(n, x + 2 * y - 1);
    dp[0][x] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= x + y; j++) {
            if (i < y) {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + j + 1);
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]);
            }
            else {
                if (j > 0) dp[i+1][j-1] = max(dp[i+1][j-1], dp[i][j] + j);
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i <= x + y; i++) ans = max(ans, dp[n][i]);
    return ans;
}

不妨在 $1 \sim 10$ 的范围内暴力枚举 $x, y$，对每个 $(x, y)$ 再从 $1 \sim x + 2y - 1$ 暴力枚举 $n$：

int main() {
    for (int x = 1; x <= 10; x++) {
        for (int y = 1; y <= 10; y++) {
            printf("x=%d, y=%d\n", x, y);
            for (int n = 1; n <= x + 2 * y - 1; n++) printf("n=%2d:%3lld\n", n, solve(n, x, y));
            putchar('\n');
        }
    }
    return 0;
}

注意到，当 $x, y$ 确定时，随着 $n$ 的增大，答案分批地呈现出一定的规律。下面以两组为例：

首先，最明显的是 $n$ 比较小的情形，这个时候答案总是 $n(x+1)$。结合多组数据可以注意到，这里 $n$ 的范围是 $n \le \min(x + 2, y)$。

当 $n$ 继续增大时，考虑相邻两项的差。

例如，对于 $x=3, y=9$，从 $n = 6$ 开始，每一项与前一项的差分别为 $(4, 4, \cdots , 4), 5, 5, 6, \color \red 6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1$。

对于 $x=10, y=4$，从 $n = 5$ 开始，每一项与前一项的差分别为 $(11, 11, \cdots , 11), 10, 9, 8, 7, 6, 5, 4, \color \red 3, 3, 2, 2, 1, 1$。

对于 $x=4, y=3$，从 $n = 4$ 开始，每一项与前一项的差分别为 $(5, 5, \cdots , 5), 4, 3, \color \red 2, 2, 1, 1$。

对于 $x=5, y=6$，从 $n = 7$ 开始，每一项与前一项的差分别为 $(6, 6, \cdots , 6), \color \red 5, 5, 4, 4, 3, 3, 2, 2, 1, 1$。

不难发现，标红位置处是一个分界点，而此时 $n$ 恰好是 $\max{x + 2, y}$。

注意到，这种邻项差构成等差数列的数列可以由 $a_n = \frac{n(n+1)}{2}$ （$a_n - a_{n-1} = n$）转化获得；而这种邻项差构成每两项成等差数列的数列（如 ${5, 5, 6, 6, 7, 7, \cdots}$）可以由 $b_n = \lfloor \frac{n^2}{4} \rfloor$ （$b_{2k} - b_{2k-1} = \lfloor \frac{(2k)^2}{4} \rfloor - \lfloor \frac{(2k-1)^2}{4} \rfloor = k^2 - \lfloor (k - \frac{1}{2})^2 \rfloor = k^2 - \lfloor k^2 - k + \frac{1}{4} \rfloor = k$，$b_{2k+1} - b_{2k} = \lfloor \frac{(2k+1)^2}{4} \rfloor - \lfloor \frac{(2k)^2}{4} \rfloor = \lfloor k^2 + k + \frac{1}{4} \rfloor - k^2 = k$，即 $b_n - b_{n-1} = \lfloor \frac{n}{2} \rfloor$）转化获得（A002620）。同时，不难发现有 $b_n + b_{n+1} = a_n$。

归纳可知（简记 $ans_n$ 为答案）：

1. 当 $x + 2 \le y$ 时：

   i. 对于 $n \in [x + 3, y - 1]$，$ans_n - ans_{n-1} = x + 2 + \lfloor \frac{n-x-3}{2} \rfloor$。

   则

   $$
   \begin{aligned}
   ans_n &= ans_{x+2} + \sum_{i=x+3}^n (x + 2 + \lfloor \frac{i-x-3}{2} \rfloor) \cr
   &= (x+2)(x+1) + (x+2)(n-x-2) + \sum_{i=0}^{n-x-3} \lfloor \frac{i}{2} \rfloor \cr
   &= (x+2)(n-1) + \lfloor \frac{(n-x-3)^2}{4} \rfloor \cr
   &= \frac{(n+x+1)^2 - (n-x-3)^2}{4} + \lfloor \frac{(n-x-3)^2}{4} \rfloor \cr
   &= \lfloor \frac{(n+x+1)^2}{4} \rfloor
   \end{aligned}
   $$

   （特别地，当 $y \in {x + 2, x + 3}$ 时，$x + 3 \gt y - 1$，此情形无效，已包含在 $x \le \min(x + 2, y)$ 的情形内）

   ii. 对于 $n \in [y, x + 2y - 1]$，$ans_n - ans_{n-1} = \lfloor \frac{x + 2y - n + 1}{2} \rfloor$。

   则

   $$
   \begin{aligned}
   ans_n &= ans_{y-1} + \sum_{i=y}^n \lfloor \frac{x + 2y - i + 1}{2} \rfloor \cr
   &= \lfloor \frac{(x+y)^2}{4} \rfloor + \sum_{i=x+2y-n+1}^{x+y+1} \lfloor \frac{i}{2} \rfloor \cr
   &= \lfloor \frac{(x+y)^2}{4} \rfloor + \lfloor \frac{(x+y+1)^2}{4} \rfloor - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= b_{x+y} + b_{x+y+1} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= a_{x+y} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{(x+y)(x+y+1)}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{(x+y)(x+y+1)}{2} - \lfloor (\frac{x-n}{2}+y)^2 \rfloor \cr
   &= \frac{(x+y)(x+y+1)}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor + y(n-x) - y^2 \cr
   &= \frac{(x+y)(x+y+1)}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor + y(n-x) - y^2 \cr
   &= \frac{y(y+2x+1)+2y(n-x)-2y^2}{2} + \frac{x(x+1)}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor \cr
   &= \frac{y(y+1)+2ny-2y^2}{2} + \frac{x(x+1)}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor \cr
   &= \frac{(2n+1)y-y^2}{2} + \frac{x(x+1)}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor \cr
   &= -\frac{n^2-2ny+y^2+n-y}{2} + \frac{x(x+1)+n^2+n}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor \cr
   &= \frac{x(x+1)+n^2+n}{2} - \lfloor (\frac{x-n}{2})^2 \rfloor - \frac{(n-y)(n-y+1)}{2} \cr
   &= \frac{x^2}{4} - \frac{nx}{2} + \frac{n^2}{4} + \frac{x^2+2x+n^2+2nx+2n}{4} - \lfloor (\frac{x-n}{2})^2 \rfloor - \frac{(n-y)(n-y+1)}{2} \cr
   &= (\frac{x-n}{2})^2 + \frac{(n+x)^2+2(n+x)}{4} - \lfloor (\frac{x-n}{2})^2 \rfloor - \frac{(n-y)(n-y+1)}{2}
   \end{aligned}
   $$

   若 $n, x$ 同奇偶，则

   $$
   \begin{aligned}
   ans_n &= \frac{(n+x)^2+2(n+x)}{4} - \frac{(n-y)(n-y+1)}{2} \cr
   &= \lfloor \frac{(n+x)^2+2(n+x)+1}{4} \rfloor - \frac{(n-y)(n-y+1)}{2} \cr
   &= \lfloor \frac{(n+x+1)^2}{4} \rfloor - \frac{(n-y)(n-y+1)}{2}
   \end{aligned}
   $$

   若 $n, x$ 不同奇偶，则

   $$
   \begin{aligned}
   ans_n &= (\frac{x-n}{2})^2 + \frac{(n+x)^2+2(n+x)}{4} - \lfloor (\frac{x-n}{2})^2 \rfloor - \frac{(n-y)(n-y+1)}{2} \cr
   &= (\frac{x-n}{2})^2 + \frac{(n+x)^2+2(n+x)}{4} - \lfloor (\frac{x-n-1}{2})^2 + \frac{x-n-1}{2} + \frac{1}{4} \rfloor - \frac{(n-y)(n-y+1)}{2} \cr
   &= (\frac{x-n}{2})^2 + \frac{(n+x)^2+2(n+x)}{4} - (\frac{x-n-1}{2})^2 - \frac{x-n-1}{2} - \frac{(n-y)(n-y+1)}{2} \cr
   &= \frac{1}{2}(x-n-\frac{1}{2}) + \frac{(n+x)^2+2(n+x)}{4} - \frac{x-n-1}{2} - \frac{(n-y)(n-y+1)}{2} \cr
   &= \frac{1}{4} + \frac{(n+x)^2+2(n+x)}{4} - \frac{(n-y)(n-y+1)}{2} \cr
   &= \frac{(n+x+1)^2}{4} - \frac{(n-y)(n-y+1)}{2} \cr
   &= \lfloor \frac{(n+x+1)^2}{4} \rfloor - \frac{(n-y)(n-y+1)}{2}
   \end{aligned}
   $$

   因此，无论 $n, x$ 的奇偶性是否相同，均有

   $$ans_n = \lfloor \frac{(n+x+1)^2}{4} \rfloor - \frac{(n-y)(n-y+1)}{2}$$

2. 当 $x + 2 \gt y$ 时：

   i. 对于 $n \in [y + 1, x + 1]$，$ans_n - ans_{n-1} = x + y - n + 1$。

   则

   $$
   \begin{aligned}
   ans_n &= ans_y + \sum_{i=y+1}^n (x + y - i + 1) \cr
   &= y(x+1) + \sum_{i=x+y-n+1}^x i \cr
   &= y(x+1) + \frac{(2x+y-n+1)(n-y)}{2} \cr
   &= y(x+1) + x(n-y) - \frac{(y-n)(y-n+1)}{2} \cr
   &= nx+y - \frac{(y-n)(y-n+1)}{2} \cr
   &= n(x+1) - \frac{(n-y)(n-y+1)}{2} \cr
   \end{aligned}
   $$

   ii. 对于 $n \in [x + 2, x + 2y - 1]$，$ans_n - ans_{n-1} = \lfloor \frac{x + 2y - n + 1}{2} \rfloor$。

   则

   $$
   \begin{aligned}
   ans_n &= ans_{x+1} + \sum_{i=x+2}^n \lfloor \frac{x + 2y - i + 1}{2} \rfloor \cr
   &= (x+1)x+y - \frac{(y-x-1)(y-x)}{2} + \sum_{i=x+2y-n+1}^{2y-1} \lfloor \frac{i}{2} \rfloor \cr
   &= (x+1)x+y - \frac{(y-x-1)(y-x)}{2} + \lfloor \frac{(2y-1)^2}{4} \rfloor - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= (x+1)x+y - \frac{(y-x-1)(y-x)}{2} + y^2 - y - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= (x+1)x + y^2 - \frac{(y-x-1)(y-x)}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{2(x+1)x + 2y^2 - (y-x-1)(y-x)}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{2(x+1)x + 2y^2 - y(y-x) - (x+1)x + (x+1)y}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{2(x+1)x + y^2 + xy - (x+1)x + (x+1)y}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{(x+1)x + y(x+y) + (x+1)y}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \frac{(x+y)(x+y+1)}{2} - \lfloor \frac{(x+2y-n)^2}{4} \rfloor \cr
   &= \cdots \cr
   &= \lfloor \frac{(n+x+1)^2}{4} \rfloor - \frac{(n-y)(n-y+1)}{2}
   \end{aligned}
   $$

综上，对 $\forall x, y \ge 1, 1 \le n \le x + 2y - 1$，有

$$
ans(n, x, y) =
\begin{cases}
n(x + 1) & n \le \min(x + 2, y) \cr
\lfloor \frac{(n+x+1)^2}{4} \rfloor - \frac{(n-y)(n-y+1)}{2} & n \ge \max(x + 2, y) \cr
\lfloor \frac{(n+x+1)^2}{4} \rfloor & x + 2 \lt n \lt y \cr
n(x+1) - \frac{(n-y)(n-y+1)}{2} & y \lt n \lt x + 2
\end{cases}
$$

证明

接下来由果溯因。在暴力时已指出，先用磨刀石总优于后用磨刀石（性质 1）。

另外，注意到连续攻击总优于有间断地攻击（性质 2）：

假设在第 $i, j$ 回合之间攻击，而在第 $i + 1 \sim j - 1$ 回合内都没有攻击，那么不如考虑只在第 $j - 1$ 和 $j$ 回合攻击，因为这两种方案的攻击次数相同（消耗刀的攻击力相同）且回合数相同，但第 $j - 1$ 回合造成的伤害一定不小于第 $i$ 回合造成的伤害（考虑第 $i + 1 \sim j - 1$ 回合可能会磨刀）。

1. 当 $n \le y$ 时：

由性质 1，每一回合都会磨刀。另外，中途停止攻击是不优的，因为每回合都会磨刀，不存在刀的攻击力将为 $0$ 的情况。再结合性质 2，最优的方案一定是从某个回合开始攻击一直到结束。

假设从第 $k$ 回合开始攻击（中途停止攻击是不优的，因为每回合都能磨刀），那么攻击时造成的伤害恒为 $x + k$。则总伤害为

$$D(k) = (x + k)(n - k + 1) = -k^2 + (n-x+1)k + x(n+1)$$

对称轴为 $k = \frac{n-x+1}{2}$。

令 $f(n) = D_{\max}$，则：

i. 当 $\frac{n-x+1}{2} \le 1.5$ （即 $n \le x + 2$）时，$f(n) = D(1) = -1+n-x+1+x(n+1) = n(x+1)$。

ii. 当 $\frac{n-x+1}{2} \gt 1.5$ （即 $n \gt x + 2$）时

$$
\begin{aligned}
f(n) &= D(\lfloor \frac{n-x+1}{2} \rfloor) \cr
&= -(\lfloor \frac{n-x+1}{2} \rfloor)^2 + (n-x+1) \lfloor \frac{n-x+1}{2} \rfloor + x(n+1) \cr
&= \lfloor \frac{n-x+1}{2} \rfloor(n-x+1 - \lfloor \frac{n-x+1}{2} \rfloor) + x(n+1) \cr
&= \lfloor \frac{n-x+1}{2} \rfloor \lceil \frac{n-x+1}{2} \rceil + x(n+1) \cr
&= \lfloor \frac{(n-x+1)^2}{4} \rfloor + x(n+1) \cr
&= \lfloor \frac{(n-x+1)^2}{4} \rfloor + \frac{(n+x+1)^2}{4} - \frac{(n-x+1)^2}{4} \cr
&= \lfloor \frac{(n+x+1)^2}{4} \rfloor
\end{aligned}
$$

2. 当 $y \lt n \le x + 2y - 1$ 时：

我们在情形 1（$n \le y$）中指出中途停止攻击是不优的。类似地，当 $n \gt y$ 时，如果中途停止攻击，那只能是因为磨刀石和刀攻击力都消耗完了，否则就相当于是在浪费回合。所以最优策略依然是从某个回合 $k$ （$k \le y$）开始攻击，只不过这里的瓶颈除了回合数不足，还有可能是刀的攻击力降为 $0$。

先考虑 $y’ = n$ 的情形。此时策略与情形 1 是相同的，造成的总伤害的极大值点为：

$$
k =
\begin{cases}
1 & n \le x + 2 \cr
\min(y, \lfloor \frac{n-x+1}{2} \rfloor) = \lfloor \frac{\min(n, x + 2y - 1) - x + 1}{2} \rfloor = \lfloor \frac{n-x+1}{2} \rfloor & n \gt x + 2
\end{cases}
$$

但我们把 $y$ 变成了 $n$，所以需要扣除多算的伤害。从第 $y + 1$ 回合开始，真正的攻击力从 $x + k - 1, x + k - 2, \cdots$ 依次递减，而它们都被当作 $x + k - 1$ 来算，所以需依次扣除 $1, 2, 3, \cdots$ 才能得到真正的总伤害。

设第 $i$ 个回合时，攻击力会降为 $0$。则 $x + k - (i - y) = 0$，即 $i = x + y + k$。考察 $i - n = x + y + k - n$ 的符号：

i. 当 $n \le x + 2$ 时：

• 若 $y = 1$，则 $i - n = x - n + 2 \ge 0$。
• 若 $y \gt 1$，则 $n \le x + 2 \le x + y$，$i - n = x + y + k - n \ge n + k - n \gt 0$。

ii. 当 $n \gt x + 2$ 时：

$$
\begin{aligned}
i - n &= x + y + \lfloor \frac{n-x+1}{2} \rfloor - n \cr
&= \lfloor \frac{n-x-2y+1}{2} \rfloor - n + x + 2y \cr
&\ge \lceil \frac{n-x-2y+1}{2} \rceil - (n - x - 2y + 1) \cr
&= \lceil \frac{t}{2} \rceil - t \quad (t = n - x - 2y + 1 \le 0) \cr
&\ge 0
\end{aligned}
$$

因此，攻击力在 $n$ 轮结束前是不会降为 $0$ 的。则造成的总伤害为

$$f(n) - \sum_{i=1}^{n-y} i = f(n) - \frac{(n-y)(n-y+1)}{2}$$

综上，

$$
f(n) =
\begin{cases}
n(x+1) & n \le x + 2 \cr
\lfloor \frac{(n+x+1)^2}{4} \rfloor & n \gt x + 2
\end{cases}
$$

$$
ans(n, x, y) =
\begin{cases}
f(n) & n \le y \cr
f(n) - \frac{(n-y)(n-y+1)}{2} & y \lt n \le x + 2y - 1
\end{cases}
$$