Znzryb's Blog
0%

2026牛客暑期多校 8——H-It's Magic, Not a Trick!（这是魔法，不是戏法！）

Posted on Edited on

题目大意

这是魔法，不是戏法！(It’s Magic, Not a Trick!)

时间限制：C/C++/Rust/Pascal 2 秒，其他语言 4 秒
空间限制：C/C++/Rust/Pascal 1024 MB，其他语言 2048 MB

“呃……真麻烦，不过真正的魔法师是不会放弃的。”

自称"超高校级的魔法师"的梦野秘密子在自己面前摆了一排共 nn 个附魔护符。第 ii 个护符最初蕴含 aia_i 单位魔力，且每个 aia_i 都是正整数。最近她研读了一本积满灰尘的古老魔导书，破译出了一个以极为特殊的方式操纵魔力的咒语。

每施放一次咒语，她必须严格按顺序执行以下两步：

  1. 注魔：选择任意一个护符，向其中注入恰好 11 单位自身的魔力，使该护符的魔力增加 11。

  2. 释放：选择任意一个在注魔完成之后魔力至少为 xx 的护符，爆发出耀眼的光芒，从该护符中消耗恰好 xx 单位魔力，使其魔力减少 xx。两步可以选择同一个护符，也可以选择不同的护符，咒语在这一点上是灵活的。

但有一条关键限制：如果注魔完成之后不存在魔力至少为 xx 的护符，则释放无法进行。此时整个咒语直接失效，什么都不会发生，她试图注魔的那个护符的魔力也保持不变。

只要每一次尝试都能成功、且所有护符的魔力始终保持非负，秘密子就可以任意多次地施放这个咒语。她好奇自己法术的极限：通过选择每次注魔与释放的位置，所有护符剩余魔力之和最小可能是多少？

比起自己算术，她更想去睡一觉，于是她向你——她可靠的助手——求助。由于答案可能很大，你只需要输出答案对 998244353998244353 取模的结果。

每个测试点包含多组测试数据。

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试数据的组数。接下来是各组测试数据的描述。

每组测试数据的第一行包含两个整数 nn 和 xx（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5，1≤x≤1091 \le x \le 10^9）。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n（1≤ai≤10181 \le a_i \le 10^{18}）。

保证所有测试数据中 nn 的总和不超过 2⋅1052 \cdot 10^5。

对于每组测试数据，输出一个整数——所有护符剩余魔力之和的最小可能值对 998244353998244353 取模的结果。

1
2
3
4
5
6
7
3
3 3
1 1 1
1 4
3
4 10
30 8 7 6
1
2
3
3
0
6

第一组数据：x=3x = 3，所有护符魔力均为 11。无论向哪个护符注魔，注魔后魔力最大也只有 2<32 < 3，无法进行释放，因此秘密子一次咒语也无法施放，剩余魔力之和为 1+1+1=31 + 1 + 1 = 3。

第二组数据：只有一个护符，魔力为 33，x=4x = 4。对该护符注魔得到 44，再对它自身释放，魔力变为 00。此后无法继续施放，答案为 00。

第三组数据：x=10x = 10，初始魔力为 [30,8,7,6][30, 8, 7, 6]。可以按如下方式施放 55 次咒语：

次数 注魔对象 释放对象 操作后的魔力序列
1 第 22 个（8→98 \to 9） 第 11 个（30→2030 \to 20） [20,9,7,6][20, 9, 7, 6]
2 第 22 个（9→109 \to 10） 第 11 个（20→1020 \to 10） [10,10,7,6][10, 10, 7, 6]
3 第 33 个（7→87 \to 8） 第 11 个（10→010 \to 0） [0,10,8,6][0, 10, 8, 6]
4 第 33 个（8→98 \to 9） 第 22 个（10→010 \to 0） [0,0,9,6][0, 0, 9, 6]
5 第 33 个（9→109 \to 10） 第 33 个（10→010 \to 0） [0,0,0,6][0, 0, 0, 6]

此时剩余魔力之和为 66，且无法再继续施放咒语，因此答案为 66。

思路讲解

初始放电次数：

1
2
3
4
5
6
7
8
9
10
// ---------------- 3. 提取“免费放电次数” = “初始注入预算” ----------------
// cnt：光靠已有能量就能完成的放电次数 sum(a_i / x)。
// 这 cnt 次施法各自附带的那个 +1 可以任意投放，所以 cnt 同时就是可支配的预算。
// 取模后 a[i] 只保留余数 r_i ∈ [0, x-1]。
i128 cnt = 0;
for (int i = 0; i < n; i++)
{
    cnt += a[i] / x;
    a[i] %= x;
}

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = 0; i < n; i++)
{
    // 把这个符从 r_i 抬到 x 需要 x - r_i 点，
    // 其中 1 点由“放它自己的那次施法的注入”免费提供，
    // 其实这个减少了题目难度，因为可以直接融入进 cost 里面，不用再单独拿出来算啊
    // 所以真正要从预算里掏的是 x - r_i - 1 点。
    // 特别地，r_i == x - 1 时代价为 0：即使预算为空也能白嫖一次施法。
    i128 cost = x - a[i] - 1;

    if (cost <= cnt)
    {
        cnt -= cost; // 花掉预算
        a[i] = 0;    // 这个符被打到 0
        round++;     // 多出一次成功施法
    }
    // 由于 a 已降序 → cost 单调不减，而 cnt 单调不增，
    // 因此一旦买不起，后面全都买不起，这里其实可以直接 break。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ---------------- 5. 用剩余预算反复“复用零符” ----------------
  // 重新降序排序：被买下的都变成 0 了，排完之后 a[0] 是剩下的最大余数。
  // a[0] == 0 表示所有符都已归零。
  sort(all(a), greater<>());
 
  if (a[0] == 0) // a[0] == 0 表示所有符都已归零。
  {
    // 下面就是计算朴素情况啊
      // 全零之后想再多施一次法，只能挑一个 0 号符：
      // 从预算掏 x-1 点把它填到 x-1，再靠本次施法自带的 +1 补满 x 然后放电。
      // 所以此后每一次施法的净代价固定为 x - 1，能买几次就买几次。
      if (cnt >= x - 1)
      {
          i128 d = cnt / (x - 1);
          cnt -= (x - 1) * d;
          round += d;
      }
      // 注：若 a[0] != 0，说明它没被买下，即 x - a[0] - 1 > cnt，
      // 而 x - a[0] - 1 <= x - 2 < x - 1，故必有 cnt < x - 1，
      // 这个分支本来也会得到 d = 0 —— 判断是冗余的，保留只为语义清晰。
  }
1
2
3
4
// ---------------- 6. 输出 S - (x-1) * R ----------------
// round 最大约 1e23，(x-1) % MOD < 1e9，乘积约 1e32，仍在 i128 范围内。
// 先减可能变负，故 +MOD 再取模。
cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84457244

心路历程（WA，TLE，MLE……）