自动搬运

查看原文

来自洛谷，原作者为

	Rain_chr think twice,code once

搬运于2025-08-24 23:00:09，当前版本为作者最后更新于2024-07-26 16:20:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前情提要：本文全文都是对 @C1942huangjiaxu 题解所作的注解，加上了本人的一些思考，并将其题解中一笔带过的地方加以说明

upd: 2024.10.26 更改了一处笔误，添加了得出结论的过程。

先摆出题解中的结论：

设 $j$ 是最小满足下式的位置

$$\sum_{i=j}^{m}2^{p_i}>\sum_{a_y\le p_j} 2^{a_y}$$

如果 $j$ 存在，设 $a_x$ 是最小满足 $a_x>p_j$ 的数，答案即为

$$\sum_{i=1}^{j-1}2^{p_i}+2^{a_x}$$

否则，答案即为

$$\sum_{i=1}^{j-1}2^{p_i}$$

这个结论是怎样猜到的呢？因为我们知道，若要使选出的数之和大于等于 $k$，则必然选出的数与 $k$ 要么完全相等，要么在二进制串的一段前缀中完全相等，并在某一位中我们选定的数字这一位比 $k$ 要大，这就是结论中两种情况答案的计算方式。

接下来，本文将开始证明这一个结论。

首先证明：若位置 $j$ 不存在，那么答案是 $\sum_{i=1}^{j-1}2^{p_i}$

我们从最末尾的 $p_m$ 开始证明能够被构造出来，再以此类推归纳到 $p_1$。

首先有 $2^{p_m}\le \sum_{a_y\le p_m} 2^{a_y}$，我们可以通过如下办法构造出 $p_m$：

1. 设 $tmp=0$，从大到小依次枚举 $a_y$。如果 $tmp+2^{a_y} < p_m$,则 $tmp\gets tmp+2^{a_y}$，否则 $tmp$ 不变。

2. 进行完上述过程，可以得到一个最大的 $tmp<p_m$。因为 $a_y$ 总和是要大于 $p_m$ 的，所以可以找到一个最大没有被选中的 $a_k$，让 $tmp\gets tmp+2^{a_k}$，此时 $tmp\ge p_m$。

3. 此时观察所有小于 $a_k$ 的位置，这些数可以被 $\{2^{a_y}|a_y\le p_m\}$ 集合构造出来，所以直接减去这些数字是没有问题的，相当于把组成这些位置的 $2^{a_y}$ 删除。

4. 由此，我们就构造出来了 $2^{p_m}$。

所以，$2^{p_m}$ 是可以构造的，我们再来看 $2^{p_{m-1}}$，因为有 $2^{p_m}+2^{p_{m-1}}\le \sum_{a_y\le p_{m-1}} 2^{a_y}$，所以有 $p_{m-1}\le \sum_{a_y\le p_{m-1}} 2^{a_y}-p_m$。这就意味着，排除掉我们刚刚为了凑出 $p_m$ 而使用的数字，剩下的数字仍然可以凑出 $p_{m-1}$。以此类推，我们就可以证明整个序列都可以被构造出来。

最后证明原结论

仍然可以尝试归纳，从最末尾的 $p_{j-1}$ 开始证明可以被构造，以此类推归纳可得到 $\{p_k|1<k<j\}$ 都可以被构造。

首先有

$$\begin{cases} \sum_{i=j}^{m}2^{p_i} > \sum_{a_y\le p_j} 2^{a_y} \\ \sum_{i=j}^{m}2^{p_i}+2^{p_{j-1}} \le \sum_{a_y\le p_{j-1}} 2^{a_y} \end{cases} $$

我们要证明的是：

$$\sum_{i=j-1}^{m}2^{p_i}\le \sum_{a_y\le p_{j-1}} 2^{a_y}-2^{a_x} $$

因为为了覆盖掉 $j$ 后面的位数，我们需要用到 $2^{a_x}$ 保证我们的数字比给出的大，所以 $2^{a_x}$ 就无法再被使用了。

我们来比较不等式两边的变化量：

左边变化量是 $2^{p_j-1}$，右边的变化量是 $\sum_{p_j<a_y\le p_{j-1}} 2^{a_y}$。由于变化之后左边从大于变成小于等于右边，所以有 $\sum_{p_j<a_y\le p_{j-1}} 2^{a_y}> 2^{p_j-1}$。

因为我们知道，$\sum_{p_j<a_y\le p_{j-1}} 2^{a_y}\ge 2^{p_j-1}$，意味着 $p_{j-1}$ 可以被 $\{a_y|p_j<a_y\le p_{j-1} \}$ 构造出来；而大于号就意味着构造出来了后，还有剩余的数字没有用完，就正好可以作为 $2^{a_x}$ 使用。

所以 $2^{p_{j-1}}$ 可以被构造。以此类推，所有的数字都可以被构造出来。

所以，结论得证。

具体实现

本来以为证明结论之后，代码比较好写，结果发现自己竟然不会比较两个求和式的大小，所以与第一篇题解作者交流之后，参考了第一篇题解的实现方式，并加以具体说明。

我们现在要来比较 $\sum_{i=j}^{m}2^{p_i}$ 与 $\sum_{a_y\le p_j} 2^{a_y}$ 的大小。

一个整体的思路是，我们先比较两者的最高位，如果最高位相同，我们就可以比较 $2^{a_y}$ 总和中第 $p_j$ 位以后组成的字符串和 $p_j$ 以后所有数加起来得到的二进制字符串的大小。这样做的原因是，总和中第 $p_j$ 位以后组成的字符串一定都是由 $\{2^{a_y}|a_y\le p_j\}$ 加起来得到的，且这个集合中的数的贡献全部在第 $p_j$ 位以后组成的字符串中，所以比较原式大小等价于比较总和第 $p_j$ 位以后组成的字符串大小。

具体地，我们设 $f_i$ 表示总和中第 $p_j$ 位以后组成的字符串是否大于等于 $p_j$ 以后所有数加起来得到的二进制字符串。

首先，如果总和的第 $p_j$ 位是 0，没得说，总和中第 $p_j$ 位以后组成的字符串一定小于 $p_j$ 以后所有数加起来得到的二进制字符串。

否则，如果存在 $p_{j+1}<a_y<p_j$，那么这个 $2^{a_y}$ 可以覆盖掉后面的 $p_{j+1}$，所以总和中第 $p_j$ 位以后组成的字符串一定大于 $p_j$。

如果以上两者都不满足，那么很显然，$f_j=f_{j+1}$。

再综合一下，我们可以得到如果这个 $j$ 不满足条件，需要满足下列两个条件:

1. $Max_{p_j}\le p_j$，否则根本没得比

2. $f_j=0$，表示总和中第 $p_j$ 位以后组成的字符串小于 $p_j$ 以后所有数加起来得到的二进制字符串。

由此，我们就可以找到最小的不合法的 $j$ 了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e6+30;
int a[N];
bool use[N];
int Max[N];//用小于等于x的数字构成的最高位
int nxt[N];//全部加起来中的第一个大于等于x的位
int p[N];
bool f[N]; //f并不代表这一个位置是否满足条件，而代表 A[pi,0] 的后缀 <= P[pi,m] 的后缀
int Pow[N];
signed main()
{  
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,q;
    cin>>n>>q;
    set<int> st;
    for(int i=1;i<=n;i++) cin>>a[i],st.insert(a[i]);
    Pow[0]=1;
    for(int i=1;i<=1e6+20;i++) Pow[i]=(Pow[i-1]<<1)>=mod?(Pow[i-1]<<1)-mod:(Pow[i-1]<<1);
    sort(a+1,a+1+n);
    int pp=1,now=-1;
    for(int i=0;i<=1e6+20;i++)
    {
        while(a[pp]<=i&&pp<=n)
        {
            int t=a[pp];
            while(use[t]) use[t]=0,t++;
            use[t]=1,now=max(now,t);
            pp++;
        }
        Max[i]=now;
    }
    nxt[1000021]=-1;
    for(int i=1e6+20;i>=0;i--)
    {
        if(use[i]) nxt[i]=i;
        else nxt[i]=nxt[i+1];
    }
    while(q--)
    {
        int m;
        cin>>m;
        for(int i=1;i<=m;i++) cin>>p[i];
        f[m+1]=1;
        int j=m+1;
        for(int i=m;i;i--)
        {
            if(!use[p[i]]) f[i]=0;
            else f[i]=f[i+1]|(i<m&&nxt[p[i+1]+1]<p[i]);
            if(!f[i]&&Max[p[i]]<=p[i]) j=i;
        }
        long long ans=0;
        for(int i=1;i<j;i++) ans+=Pow[p[i]];
        if(j<=m)
        {
            if(st.upper_bound(p[j])==st.end()) ans=-1;
            else ans+=Pow[*st.upper_bound(p[j])];
        }
        cout<<ans%mod<<'\n';
    }
	return 0;
}