2026牛客暑期多校 8——H-It's Magic, Not a Trick!(这是魔法,不是戏法!) · znzryb
## 题目大意
### 这是魔法,不是戏法!(It's Magic, Not a Trick!)
时间限制:C/C++/Rust/Pascal 2 秒,其他语言 4 秒
空间限制:C/C++/Rust/Pascal 1024 MB,其他语言 2048 MB
<!-- Notion block type: heading_4 -->
*"呃……真麻烦,不过真正的魔法师是不会放弃的。"*
自称"超高校级的魔法师"的梦野秘密子在自己面前摆了一排共 $n$ 个附魔护符。第 $i$ 个护符最初蕴含 $a_i$ 单位魔力,且每个 $a_i$ 都是正整数。最近她研读了一本积满灰尘的古老魔导书,破译出了一个以极为特殊的方式操纵魔力的咒语。
每施放一次咒语,她必须严格按顺序执行以下两步:
1. **注魔**:选择任意一个护符,向其中注入恰好 $1$ 单位自身的魔力,使该护符的魔力增加 $1$。
1. **释放**:选择任意一个在注魔完成之后魔力**至少为** $x$ 的护符,爆发出耀眼的光芒,从该护符中消耗恰好 $x$ 单位魔力,使其魔力减少 $x$。两步可以选择同一个护符,也可以选择不同的护符,咒语在这一点上是灵活的。
但有一条关键限制:如果注魔完成之后不存在魔力至少为 $x$ 的护符,则释放无法进行。此时整个咒语直接失效,什么都不会发生,她试图注魔的那个护符的魔力也保持不变。
只要每一次尝试都能成功、且所有护符的魔力始终保持非负,秘密子就可以任意多次地施放这个咒语。她好奇自己法术的极限:通过选择每次注魔与释放的位置,所有护符剩余魔力之和最小可能是多少?
比起自己算术,她更想去睡一觉,于是她向你——她可靠的助手——求助。由于答案可能很大,你只需要输出答案对 $998244353$ 取模的结果。
<!-- Notion block type: heading_4 -->
每个测试点包含多组测试数据。
第一行包含一个整数 $t$($1 \le t \le 10^4$),表示测试数据的组数。接下来是各组测试数据的描述。
每组测试数据的第一行包含两个整数 $n$ 和 $x$($1 \le n \le 2 \cdot 10^5$,$1 \le x \le 10^9$)。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$($1 \le a_i \le 10^{18}$)。
保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。
<!-- Notion block type: heading_4 -->
对于每组测试数据,输出一个整数——所有护符剩余魔力之和的最小可能值对 $998244353$ 取模的结果。
<!-- Notion block type: heading_4 -->
<!-- Notion block type: heading_4 -->
```
3
3 3
1 1 1
1 4
3
4 10
30 8 7 6
```
<!-- Notion block type: heading_4 -->
```
3
0
6
```
<!-- Notion block type: heading_4 -->
**第一组数据**:$x = 3$,所有护符魔力均为 $1$。无论向哪个护符注魔,注魔后魔力最大也只有 $2 < 3$,无法进行释放,因此秘密子一次咒语也无法施放,剩余魔力之和为 $1 + 1 + 1 = 3$。
**第二组数据**:只有一个护符,魔力为 $3$,$x = 4$。对该护符注魔得到 $4$,再对它自身释放,魔力变为 $0$。此后无法继续施放,答案为 $0$。
**第三组数据**:$x = 10$,初始魔力为 $[30, 8, 7, 6]$。可以按如下方式施放 $5$ 次咒语:
| 次数 | 注魔对象 | 释放对象 | 操作后的魔力序列 |
| --- | --- | --- | --- |
| 1 | 第 $2$ 个($8 \to 9$) | 第 $1$ 个($30 \to 20$) | $[20, 9, 7, 6]$ |
| 2 | 第 $2$ 个($9 \to 10$) | 第 $1$ 个($20 \to 10$) | $[10, 10, 7, 6]$ |
| 3 | 第 $3$ 个($7 \to 8$) | 第 $1$ 个($10 \to 0$) | $[0, 10, 8, 6]$ |
| 4 | 第 $3$ 个($8 \to 9$) | 第 $2$ 个($10 \to 0$) | $[0, 0, 9, 6]$ |
| 5 | 第 $3$ 个($9 \to 10$) | 第 $3$ 个($10 \to 0$) | $[0, 0, 0, 6]$ |
此时剩余魔力之和为 $6$,且无法再继续施放咒语,因此答案为 $6$。
## 思路讲解
初始放电次数:
```cpp
// ---------------- 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;
}
```

```cpp
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。
}
```
```cpp
// ---------------- 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 —— 判断是冗余的,保留只为语义清晰。
}
```
```cpp
// ---------------- 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](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=84457244)
::: 源代码(队友的 AC 提交)
```cpp
// teamname: Gospel_rock
// Acmer: 鵗曦(xixii_)
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
constexpr const ll INF = 1e18, MOD = 998244353;
constexpr const ld EPS = 1e-7;
// #define int long long
#define all(x) x.begin(), x.end()
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << (a)[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug(x) cerr << "[" << #x << "] = " << (x) << "\n"
static int last_res;
ostream &operator<<(ostream &os, __int128_t x)
{
if (x < 0)
os << '-', x = -x;
if (x > 9)
os << x / 10;
return os << (char)('0' + x % 10);
}
istream &operator>>(istream &is, __int128_t &x)
{
string s;
if (!(is >> s))
return is;
x = 0;
size_t i = 0;
bool neg = false;
if (s[0] == '-')
{
neg = true;
i = 1;
}
else if (s[0] == '+')
{
i = 1;
}
for (; i < s.size(); i++)
x = x * 10 + (s[i] - '0');
if (neg)
x = -x;
return is;
}
void solve()
{
ll n, x;
cin >> n >> x;
vector<i128> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
i128 cnt = 0;
i128 sum = 0;
for (int i = 0; i < n; i++)
{
sum = (sum + a[i]) % MOD;
}
if (x == 1)
{
cout << sum << "\n";
return;
}
for (int i = 0; i < n; i++)
{
cnt += a[i] / x;
a[i] %= x;
}
i128 round = cnt;
sort(all(a), greater<>());
for (int i = 0; i < n; i++)
{
i128 cost = x - a[i] - 1;
if (cost <= cnt)
{
cnt -= cost;
a[i] = 0;
round++;
}
}
sort(all(a), greater<>());
if (a[0] == 0)
{
if (cnt >= x - 1)
{
i128 d = cnt /(x - 1);
cnt -= (x - 1) * d;
round += d;
}
}
cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
```
:::
::: AI 注释队友代码版
```cpp
// teamname: Gospel_rock
// Acmer: 鵗曦(xixii_)
//
// 题目:2026 牛客暑期多校 8 - H. It's Magic, Not a Trick!
//
// ============================ 题意 ============================
// n 个符,第 i 个初始能量 a_i(正整数)。一次“施法”必须按顺序做两步:
// 1) 注入:任选一个符 +1;
// 2) 放电:任选一个此刻能量 >= x 的符 -x(可以就是刚才注入的那个)。
// 若注入后不存在能量 >= x 的符,则整次施法失败(什么都不发生)。
// 问:任意安排注入/放电位置,最终总能量的最小值是多少(对 998244353 取模)。
//
// ============================ 思路 ============================
// 【第 0 步】一次成功的施法让总能量恰好减少 (x - 1),与注入到哪、从哪放电无关。
// 设最多能成功施法 R 次,则答案 = S - (x-1) * R,其中 S = sum(a_i)。
// 所以整题只需最大化 R。
//
// 【第 1 步】记账模型。R 次施法 = R 个 “+1” 的注入 + R 次放电。
// 把放电归属到具体的符:符 i 收到 b_i 点注入、被放电 d_i 次,则要求
// a_i + b_i >= x * d_i,且 sum(b_i) = sum(d_i) = R。
// 即:注入总量本身就等于施法次数——这是一个“自举”的预算系统。
//
// 【第 2 步】免费的部分。cnt0 = sum(a_i / x) 次放电不用任何额外注入就能完成。
// 而这 cnt0 次施法各自附带的那个 “+1” 可以随便扔到任何地方,
// 所以 cnt0 同时是我们可自由调度的【注入预算】。
// 把 a_i 取模,余数 r_i = a_i % x ∈ [0, x-1]。
//
// 【第 3 步】价目表。想让余数为 r 的符多放一次电,需要把它从 r 抬到 x,共 x - r 点。
// 其中最后 1 点由【放它自己的那次施法的注入】提供(注入和放电是同一次施法的两步,
// 且允许作用于同一个符),所以真正从预算里掏的是:
// 第一次把某个符打到 0:净代价 x - r_i - 1
// 之后在同一个(已经是 0 的)符上再放一次电:净代价 x - 0 - 1 = x - 1
// 由于 x - r_i - 1 <= x - 1 恒成立,所有“第一次”都不比任何“第二次”贵。
// 每笔购买的收益都恰好是 “+1 次施法”,收益相同就只看价格 → 按代价升序贪心即最优,
// 而代价升序 <=> 余数降序,所以把余数从大到小排序后依次买即可。
//
// 【第 4 步】顺序可行性。预算的物理含义是“还剩几次可以立刻执行的放电”。
// 每花 1 点预算就真的执行一次施法:放电落在某个能量 >= x 的符上(还有预算就说明存在),
// 注入则定向浇到正在攒的目标符上。攒到 x-1 后,下一次施法直接把目标符注入到 x 并放电,
// 这一次不消耗预算,正好对应记账里“免费的那一发”。故计数与真实操作序列一一对应。
//
// 复杂度:O(n log n) / 组,瓶颈是排序。
// ==============================================================
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
constexpr const ll INF = 1e18, MOD = 998244353;
constexpr const ld EPS = 1e-7;
// #define int long long
#define all(x) x.begin(), x.end()
// ------------------------- 调试宏(比赛模板,与算法无关) -------------------------
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << (a)[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug(x) cerr << "[" << #x << "] = " << (x) << "\n"
static int last_res;
// ------------------------- __int128 的输入输出重载 -------------------------
// a_i <= 1e18 用 long long 够用,但中间量 cnt / round 可能达到 1e23 量级,
// 因此整份代码统一用 i128 存能量,这里补上流运算符。
ostream &operator<<(ostream &os, __int128_t x)
{
if (x < 0)
os << '-', x = -x;
if (x > 9)
os << x / 10;
return os << (char)('0' + x % 10);
}
istream &operator>>(istream &is, __int128_t &x)
{
string s;
if (!(is >> s))
return is;
x = 0;
size_t i = 0;
bool neg = false;
if (s[0] == '-')
{
neg = true;
i = 1;
}
else if (s[0] == '+')
{
i = 1;
}
for (; i < s.size(); i++)
x = x * 10 + (s[i] - '0');
if (neg)
x = -x;
return is;
}
void solve()
{
ll n, x;
cin >> n >> x;
vector<i128> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
// ---------------- 1. 先把初始总能量 S 在取模意义下算出来 ----------------
// 注意必须在修改 a 之前算,因为后面 a 会被取模成余数。
// 最终答案 = S - (x - 1) * R (mod 998244353)。
i128 sum = 0;
for (int i = 0; i < n; i++)
{
sum = (sum + a[i]) % MOD;
}
// ---------------- 2. 特判 x == 1 ----------------
// 每次施法 = +1 再 -1,总能量恒定不变,做多少次都没有收益(x - 1 = 0)。
// 同时也避免了后面除以 (x - 1) 时的除零。
if (x == 1)
{
cout << sum << "\n";
return;
}
// ---------------- 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;
}
// round:累计的施法总次数 R,初值就是这些白拿的放电。
i128 round = cnt;
// ---------------- 4. 贪心买“第一次”:把余数大的符优先打到 0 ----------------
// 余数越大 → 补到 x 需要的注入越少 → 代价越低,所以按余数降序处理。
sort(all(a), greater<>());
for (int i = 0; i < n; i++)
{
// 把这个符从 r_i 抬到 x 需要 x - r_i 点,
// 其中 1 点由“放它自己的那次施法的注入”免费提供,
// 所以真正要从预算里掏的是 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。
}
// ---------------- 5. 用剩余预算反复“复用零符” ----------------
// 重新降序排序:被买下的都变成 0 了,排完之后 a[0] 是剩下的最大余数。
// a[0] == 0 表示所有符都已归零。
sort(all(a), greater<>());
if (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 —— 判断是冗余的,保留只为语义清晰。
}
// ---------------- 6. 输出 S - (x-1) * R ----------------
// round 最大约 1e23,(x-1) % MOD < 1e9,乘积约 1e32,仍在 i128 范围内。
// 先减可能变负,故 +MOD 再取模。
cout << (sum - (x - 1) % MOD * round % MOD + MOD) % MOD << "\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
```
:::
## 心路历程(WA,TLE,MLE……)