P10675 【MX-S1-T4】先见之明 题解注解

· · 题解

前情提要：本文全文都是对 @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 不满足条件，需要满足下列两个条件:

由此，我们就可以找到最小的不合法的 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;
}