P11835 封印题解

隔壁泞2的如心 · 2025-03-03 16:38:13 · 题解

完蛋了我被封印了功力只剩一成

这题最重要的一步在于——

不妨令 m 为整个数列的最大值。称所有 m 以及最后一个 m 后的所有 m-1 所在的位置为关键的，即图中红框内的数。我们发现，无论如何操作，关键的位置数量永远不会变化，除非这些位置上的数一直被删到了 0。

同时，我们可以发现，给定一个经过一系列操作的数列，那么它的每个关键位置在原数列的位置是可以被计算出来的。也就是说，这些关键位置虽然值可能相同，但它们其实是可以被视为是两两不同的！这样，我们成功回避了此题的去重灾难。

——这大概就是这题的封印。如果没注意到这一步却强行做这题会导致你指望着自动机上 dp、功力只剩一成、余生在阿巴阿巴中度过……

接下来先考虑两个关键位置之间的数被移到后面之后，后面留下来的数应该是这个前缀整体 -1 的一个子序列。可并非所有的子序列都满足条件。我们可以发现，如果在上图中给每个数向其左边的第一个不小于它的数连边，则会连成一棵树。那么如果一个数被留下来，则它在这棵树上的父亲也一定会留下来。同时，由于一个数的每个儿子的数值都是不同的，因此凡是满足上述条件的子序列都一定是满足条件且两两不同的！

这样的话，当这个数列已经被操作过一整轮之后，任意两个关键位置之间的数都是可以按照上述规则独立选取的！所以我们可以对于每个关键位置和整数 h 求出“在它到下一个关键位置间的区域选取数，且被选的数不小于 h ”的方案数。这个方案可以直接 dp 算出，再以 O(nm) 的时间复杂度合并答案就可以啦！

可是，这个做法面临着很多很多的细节……比如说在数列未被操作完一整轮时，有些关键位置间的数是没被操作过的，所以这里要特别处理一下。

为了方便考虑，我们把原数组不断地整体减一、删去 0 再接到原数组后面。

我的代码里分了三个阶段计数。稍微详细地说一下吧（

第一个阶段对应图中蓝色的区域，此时原数列中还有数没被删除过，对于每个 1 \le i \le n-1 算出“原数组的前 i 个数已被挪到了后面，而后 n-i 个数未被操作过时可以生成数列的种数”。
第三个阶段对应图中紫色的区域，第一个关键位置已经第二次被操作，这时所有关键位置独立且等价。有一个关键位置之后的数会跨过数列首尾，其他的关键未知间的数可以随便选。这里我枚举了新数列的结尾是在原数列的哪个关键位置后，然后用 dp 对这个关键位置求出“它到下一个关键位置间的区域选取数，且额外标记一个被选的数，被选的数不小于 h-1，被标记的数及其之前的被选的数不小于 h”的方案数。这个被标记的数就是被钦定的数组结尾。
第二阶段作为过渡，对于最后一个关键位置到第二次出现的第一个关键位置之间的选数方案进行统计，这里的做法和第三阶段类似，不过这里被钦定的数组结尾的下标必须不小于 n。
需要注意原数组以 2 开头、以 1 结尾的特殊情况，就是这个情况把两篇题解都卡掉了。由于 1 无法被挪到后面，会被直接删除，所以按照这个方法会出现算重的情况。我的处理方法是将第二阶段提前到原数组的最后一个非 1 位置，这样避免了跨阶段处理连续的 1 ，就可以通过了（

这是代码：

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
#define FSIZ 407693
#define add(a,b) (a+=(b),a>=mod?a-=mod:0)
#define neg(x) ((x)&1?mod-1:1)
#define Q(a,b) C((a)+(b)-1,(b)-1)
#define cond(a,b)((a)?(b):0)
using namespace std;
int fac[FSIZ],ifac[FSIZ],inv[FSIZ];
int C(int n1,int m1){
    if(m1<0||m1>n1)return 0;
    return fac[n1]*ifac[m1]%mod*ifac[n1-m1]%mod;
}
inline int qpow(int n1,int n2){
    int n3=n1,n4=1;
    while(n2){
        if(n2&1)n4*=n3,n4%=mod;
        n3*=n3,n3%=mod;n2>>=1;
    }return n4;
}
inline int mut(initializer_list<int> arg){
    int ret=1;
    for(auto i:arg)ret*=i,ret%=mod;
    return ret;
}
int c,t,n,m;
int a[5016],icp[5016],pci[5016],dp0[5016],dp1[5016][2][2],fa0[5016],ins[5016],dp[5016][2600][2],pfmut[2600][2600],sfmut[2600][2600];
int sta[5016],tp=0;
vector<int> sn[5016];
void recurupd(int now){
    dp0[now]=1;
    for(auto to:sn[now])dp0[now]=dp0[now]*(dp0[to]+(!(ins[to]||a[to]==1)))%mod;
    if(now==0)return;
    recurupd(fa0[now]);
}
signed main(){
    fac[0]=1;for(int i=1;i<=FSIZ-1;i++)fac[i]=fac[i-1]*i%mod;
    ifac[FSIZ-1]=qpow(fac[FSIZ-1],mod-2);for(int i=FSIZ-1;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;
    inv[0]=0;for(int i=1;i<=FSIZ-1;i++)inv[i]=ifac[i]*fac[i-1]%mod;
    scanf("%lld%lld",&c,&t);
    while(t--){
        memset(a,0,sizeof(a));memset(icp,0,sizeof(icp));memset(pci,0,sizeof(pci));
        memset(dp0,0,sizeof(dp0));memset(dp1,0,sizeof(dp1));memset(ins,0,sizeof(ins));
        memset(dp,0,sizeof(dp));memset(pfmut,0,sizeof(pfmut));memset(sfmut,0,sizeof(sfmut));
        memset(fa0,0,sizeof(fa0));
        for(int i=0;i<=5010;i++)sn[i].clear(),sn[i].shrink_to_fit();
        scanf("%lld%lld",&n,&m);m=0;
        for(int i=1;i<=n;i++)scanf("%lld",a+i);
        for(int i=1;i<=n;i++)m=max(m,a[i]);
        if(m==1){
            printf("%lld\n",n);
            continue;
        }
        int lasp=0,pcc=0,coef=0;
        for(int i=1;i<=n;i++){
            if(a[i]==m){
                lasp=i;icp[i]=1;pci[++pcc]=i;
            }
        }
        coef=pcc;
        for(int i=lasp+1;i<=n;i++){
            if(a[i]==m-1){
                icp[i]=1;pci[++pcc]=i;
            }
        }
        //for(int i=1;i<=pcc;i++)printf("%lld ",pci[i]);printf("!!!!\n");
        int n0=n;while(a[n]==1)n--;
        for(int i=1;!icp[i];i++){
            a[++n0]=a[i]-1;
        }
        int ans=0;
        //第一阶段
        tp=0;dp0[0]=1;a[0]=m+1;sta[++tp]=0;ins[0]=1;
        for(int i=1;i<=n0;i++){
            int pop0=sta[tp];
            while(tp&&a[sta[tp]]<a[i])ins[sta[tp--]]=0;
            if(!ins[pop0])recurupd(pop0);
            fa0[i]=sta[tp];ins[sta[++tp]=i]=1;
            sn[fa0[i]].push_back(i);
            dp0[i]=1;
            recurupd(fa0[i]);
            //printf("*%lld %lld\n",fa0[i],dp0[0]);
            if(i<n)add(ans,dp0[0]);
        }
        //printf("solve0:%lld\n",ans);
        //第二阶段
        for(int i=1;i<=n0;i++)reverse(sn[i].begin(),sn[i].end());
        for(int i=n0;i>=pci[1];i--){
            if(a[i]==0)continue;
            if(a[i]==1){
                dp1[i][0][1]=1;
            }
            else{
                dp1[i][0][0]=1;
            }
            for(auto to:sn[i]){
                dp1[i][1][1]=dp1[i][1][1]*(dp1[to][0][0]+1)%mod;
                dp1[i][1][0]=dp1[i][1][0]*(dp1[to][0][0]+1)%mod;
                add(dp1[i][1][1],dp1[i][0][1]*(dp1[to][1][0]+dp1[to][1][1])%mod);
                add(dp1[i][1][1],dp1[i][0][0]*dp1[to][1][1]%mod);
                add(dp1[i][1][0],dp1[i][0][0]*dp1[to][1][0]%mod);
                dp1[i][0][1]=dp1[i][0][1]*(dp1[to][0][1]+dp1[to][0][0]+1)%mod;
                add(dp1[i][0][1],dp1[i][0][0]*dp1[to][0][1]%mod);
                dp1[i][0][0]=dp1[i][0][0]*(dp1[to][0][0]+1)%mod;
            }
            if(i>=n&&a[i]>1){
                add(dp1[i][1][1],dp1[i][0][1]);
                add(dp1[i][1][0],dp1[i][0][0]);
            }
            //printf("#1 %lld:%lld %lld %lld %lld",i,dp1[i][0][0],dp1[i][0][1],dp1[i][1][0],dp1[i][1][1]);printf("\n");
        }
        add(ans,(dp1[pci[1]][1][0]+dp1[pci[1]][1][1])%mod);
        //printf("solve1:%lld\n",ans);
        //第三阶段
        for(int i=n0;i>=pci[1];i--){
            //printf("%lld:",i);
            //for(auto to:sn[i])printf("%lld ",to);printf("\n");
            for(int j=0;j<=a[i];j++){
                dp[i][j][0]=1;
            }
            for(auto to:sn[i]){
                if(icp[to])continue;
                for(int j=0;j<=a[to];j++){
                    dp[i][j][1]=dp[i][j][1]*(dp[to][j][0]+1)%mod;
                }
                for(int j=0;j<a[to];j++){
                    add(dp[i][j+1][1],dp[i][j][0]*dp[to][j+1][1]%mod);
                }
                for(int j=0;j<=a[to];j++){
                    dp[i][j][0]=dp[i][j][0]*(dp[to][j][0]+1)%mod;
                }
            }
            for(int j=0;j<a[i];j++){
                add(dp[i][j+1][1],dp[i][j][0]);
            }
        }
        for(int i=0;i<=m;i++){
            pfmut[0][i]=1;
            for(int j=1;j<=pcc;j++){
                pfmut[j][i]=pfmut[j-1][i]*dp[pci[j]][i][0]%mod;
            }
            sfmut[pcc+1][i]=1;
            for(int j=pcc;j>=1;j--){
                sfmut[j][i]=sfmut[j+1][i]*dp[pci[j]][i][0]%mod;
            }
            //for(int j=1;j<=pcc;j++)printf("(%lld,%lld) ",dp[pci[j]][i][0],dp[pci[j]][i][1]);printf("\n");
            //for(int j=1;j<=pcc;j++)printf("[%lld,%lld] ",pfmut[j][i],sfmut[j][i]);printf("\n");
        }
        for(int val0=0;val0<=m;val0++){
            for(int i=1;i<=pcc;i++){
                add(ans,mut({pfmut[i-1][val0+3],sfmut[i+1][val0+2],dp[pci[i]][val0+3][1]}));
                //printf("#n %lld:%lld\n",val0,mut({pfmut[i-1][val0+3],sfmut[i+1][val0+2],dp[pci[i]][val0+3][1]}));
            }
        }
        //printf("%lld\n",ans);
        if(m>2)printf("%lld\n",(ans+pcc)%mod);
        else printf("%lld\n",(ans+coef)%mod);
    }
}
/*
10 1
3 10
2 10 1
*/
*/

抱歉……我知道我完全没讲明白。我原本真的很想好好写这篇题解的，可是我看到另一篇题解里 1k 的代码之后我一下子就布响丸辣！事实上注意到“关键位置”之后这道题对于绝大多数选手而言都是可做的了，而在细节上大家一定都有比我更好的实现（

~~需要注意民间数据里没有 m 较小的情况，所以这个做法可能会被正式数据卡，到时候再说吧（~~

这道题确实很有意思，但它的细节也是真的多。对于我这种做题全靠猜的人来说这道题简直像神一样，是不可战胜的……

其实“梦想”和“兴趣”之间完全可以是没有关系的。也许梦想会被现实破碎，但只要兴趣还在，你随时可以回来。不管你的梦想和兴趣在哪，祝你旅途愉快，愿你一路顺风。

P11835 封印 题解

P11835 封印题解