题解：P17300 [ICPC 2026 Xi'an I] Transform
lailai0916
·
·
题解
题意简述
每次可以选出当前多重集的一个子多重集，将这些元素删除，再放入所选部分的 \operatorname{mex}。求将初始多重集变为 \{k\} 所需的最少操作次数。
解题思路
先考虑最后一次操作。为了生成 k，被选中的部分必须包含 0,1,\dots,k-1，且不能包含 k。因此，问题的关键是计算每个较小数字一共需要准备多少份。
记 c_i 为初始多重集中数字 i 的个数，d_i 为整个过程中生成数字 i 的操作次数。目标只含一个 k，所以最后必须且只需生成一次 k：
d_k=1
每次生成某个大于 i 的数字，都要消耗至少一个 i。于是，所有更大数字对 i 的总需求为：
T_i=\sum_{j=i+1}^{k}d_j
数字 i 的来源只有初始的 c_i 份和操作生成的 d_i 份。要满足全部需求，必有：
c_i+d_i\ge T_i
若生成的 i 超过缺口，多出的操作不仅直接增加答案，还会继续消耗更小的数字，不可能使方案更优。因此最优取值为：
d_i=\max(0,T_i-c_i)
处理完数字 i 后，更小数字需要支撑原有的全部操作以及新增加的 d_i 次操作，所以：
T_{i-1}=T_i+\max(0,T_i-c_i)=\max(T_i,2T_i-c_i)
也就是说，当库存足够时需求不变；库存不足时，缺少的每一份都要额外生成。
初始时只有生成 k 的一次操作，因此 T_{k-1}=1。从 k-1 递推到 0 后：
T_{-1}=\sum_{i=0}^{k}d_i
这就是忽略初始数字 k 时的最少操作次数。
上述递推给出的不只是下界。可以按数字从小到大执行生成操作，并为每次生成较大数字预留一份所有更小数字。等式 c_i+d_i\ge T_i 保证每一层的库存都足够。没有被预留的重复元素可以并入某次删除，不会改变对应的 \operatorname{mex}，所以递推值一定能够达到。
接下来处理初始多重集中的 k。若初始集合已经是 \{k\}，不需要执行操作，答案为 0。否则，最后一次操作不能选中已有的 k。当递推答案至少为 2 时，可以在此前某次生成小于 k 的数字时顺便删除所有 k，因为大于当前 \operatorname{mex} 的元素不会影响结果。
若递推答案恰为 1，并且初始集合含有 k，就没有这样的前置操作。此时必须先增加一次操作删除已有的 k，再执行最终操作，故答案需要加一。
$$
T\gets 2^gT
$$
答案要对 $998244353$ 取模，但判断 $T_i\le c_i$ 必须使用真实大小。由于 $c_i\le n$，一旦 $T_i>n$，此后所有比较都会进入第二个分支。因此同时维护两个值：一个保存模意义下的答案，另一个把真实值截断为至多 $n+1$。
排序复杂度为 $O(n\log n)$。每个不同数字只进行一次递推和一次快速幂，空间复杂度为 $O(n)$。
## 正确性证明
对任意 $i<k$，所有生成大于 $i$ 的操作都必须消耗一份 $i$，所以至少需要 $T_i$ 份 $i$。初始与生成的总量为 $c_i+d_i$，由此得到下界 $d_i\ge\max(0,T_i-c_i)$。取等号会同时最小化当前操作数和传给更小数字的需求，因此从大到小递推得到的是所有方案共同的下界。
按递推值生成每种数字时，关系 $c_i+d_i\ge T_i$ 保证能够把一份 $i$ 分配给每次需要它的更大数字生成操作。依次完成所有层后，可以生成一次 $k$。其余不参与后续生成的元素都能并入适当的删除集合而不改变 $\operatorname{mex}$，故这个下界可以达到。
若递推值至少为 $2$，在最终生成 $k$ 之前必有一次生成较小数字的操作，初始的所有 $k$ 都能在该操作中删除。若递推值为 $1$ 且初始含有 $k$，最终操作无法删除它，额外一次操作既是必要的，也足以先将其清除。结合初始集合已经为 $\{k\}$ 的特判，算法覆盖了全部情况，并输出最少操作次数。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=998244353;
struct node
{
ll val,res;
};
ll Pow(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
node jump(node f,int k,int n)
{
f.res=f.res*Pow(2,k)%mod;
while(k&&f.val<=n)
{
f.val*=2;
k--;
}
if(f.val>n)f.val=n+1;
return f;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n,k;
cin>>n>>k;
vector<int>a;
bool has=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==k)has=1;
if(x<k)a.push_back(x);
}
if(n==1&&has)
{
cout<<0<<'\n';
continue;
}
sort(a.begin(),a.end(),greater<int>());
node f={1,1};
int pos=k-1;
for(int i=0;i<a.size();)
{
int j=i+1;
while(j<a.size()&&a[j]==a[i])j++;
f=jump(f,pos-a[i],n);
int c=j-i;
if(f.val>c)
{
f.val=min<ll>(n+1,2*f.val-c);
f.res=(2*f.res-c+mod)%mod;
}
pos=a[i]-1;
i=j;
}
f=jump(f,pos+1,n);
if(has&&f.val==1)f.res=f.res+1==mod?0:f.res+1;
cout<<f.res<<'\n';
}
return 0;
}
```