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

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

不妨令 $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$ 较小的情况，所以这个做法可能会被正式数据卡，到时候再说吧（

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

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

场上拼尽全力口胡出 $O(n^6)\to O(n^4)$ 还没调完，出来发现 DP 优化简直唐到没边。大败而归。

---

首先要观察最终的序列 $b$ 可能形如什么样子。

我们将 $a$ 序列扩展 $m$ 次成如下形式：

$$a_1,a_2,\dots a_{n-1},a_n,(a_1-1),(a_2-1),\dots,(a_n-1),(a_1-2),(a_2-2),\dots,(a_n-m)$$

然后选出若干下标 $p_1<p_2<p_3<\dots<p_k$，满足：

1. $p_1+n=p_k$。
2. $a_{p_i}>0$。
3. $\forall p_{i-1}<j<p_i,a_j<a_{p_i}$。
4. $\forall p_i<n,p_i+1=p_{i+1}$。

最终得到 $b=[a_{p_2},a_{p_3},\dots,a_{p_n}]$，注意这里的下标从 $2$ 开始。

这样的刻画只会遗漏 $b=a$ 的情况和 $b=[1,1,\dots,1,1]$ 的情况，最后一定要记得加上。

---

这里证明由不同 $p_{1\sim k}$ 得到的 $b$ 是互不相同的。

先忽略限制 $2,4$，在更弱的限制下证明，则原限制也一定互不相同。

考虑由 $p_{1\sim k}$ 生成的 $b_k$ 和由 $q_{1\sim k}$ 生成的 $c_k$。

若 $p_1=q_1$：

当 $b_k=c_k$ 时，由于限制 $3$，一定有 $p_i=q_i$，即 $p=q$。

若 $p_1\neq q_1$：

注意到我们生成序列 $a$ 的方式，有 $a_i>a_{i+n}$。

设 $A_i$ 为 $a_{[i+1,i+n]}$ 的非严格前缀最大值序列，则 $A_i$ 互不相同。

则 $A_{p_1}\neq A_{q_1}$，可以推出 $b\neq c$。

---

照着上面四条性质 DP 就可以获得一个多项式做法，复杂度在 $O(n^2)\sim O(n^6)$ 不等。

$p_1\leq n$ 的情况比较特殊，先 $O(n^2)$ 简单 DP 计算。

注意到 $p=[p_1,p_2,\dots,p_k]$ 满足限制 $3$ 当且仅当 $p'=[p_1+n,p_2+n,\dots p_k+n]$ 满足限制 $3$。

枚举 $k$，我们对所有满足限制 $3$ 且 $n<p_1\leq 2n$ 且 $\min(a_{p_i})=k$ 的序列 $p$ 计数，设这样的序列有 $f(k)$ 个，则它们对答案的贡献是 $k\times f(k)$。

这个枚举 $k$ 不好消掉，于是考虑枚举 $a_{p_i}$ 中最靠左的最小值位置 $x$，钦定它左边所有选择的位置 $>x$，右边所有选择的位置 $>=x$。

设 $f_i$ 表示 $p_1=i$ 的方案数，$g_i$ 表示 $p_k=i$ 的方案数。

使用单调栈优化 DP 即可快速计算 $f$。

我们需要把单调栈转置过来快速计算 $g$。

单调栈优化 DP 可以看成 $f_i\to f_{l_i\sim i-1}$，所以转置可以看成 $g_i\leftarrow g_{l_i\sim i-1}$，前缀和维护即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;'0'>ch||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;'0'<=ch&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=5050,mo=998244353;
int a[N],b[N],c[N],f[N],g[N],p,w;
inline void doing(){
	n=read();read();m=n*2;s=l=w=0;
	f(i,1,n)w=max(w,a[i]=read());
	if(w<2)return cout<<n<<"\n",void();
	f(i,1,n)if(a[i]==w)l=i;
	f(i,1,n)s+=(i<l&&a[i]==w)||(i>l&&a[i]==w-1&&w>2);//b=[1,1,...,1,1]的情况
	f(i,1,n)a[i+n]=a[i]-1;
	f(i,0,n)f[i]=0;f[0]=1;
	f(i,0,n){//p1<=n的情况(b=a的情况顺路算了)
		int pr=0;f[i]%=mo;
		f(j,i+1,n)if(a[j]>pr){
			pr=a[j];f[j]+=f[i];
			if(pr==1)break;
		}
	}
	f(i,0,n)s+=f[i];s%=mo;
	a[l=0]=N;
	g(i,m,0){//预处理单调栈
		while(l&&a[b[l]]<=a[i])c[b[l--]]=max(i-1,0ll);
		b[++l]=i;
	}
	f(x,1,m)if(p=a[x]){//枚举x计算fi,gi
		f(i,0,m)f[i]=b[i]=0;f[x]=1;
		g(i,x,1){
			f[i]+=a[i]<=p?0:b[i]%mo;
			b[c[i]]-=f[i];b[i-1]+=b[i]+f[i];
		}
		f(i,0,m)g[i]=b[i]=0;g[x]=1;
		f(i,x,m){
			g[i]+=a[i]<p?0:(b[i-1]-b[c[i]])%mo;
			b[i]=b[i-1]+g[i];
		}
		f(i,1,n)s=(s+f[i]*g[i+n]%mo*(p-1))%mo;
	}
	cout<<s<<"\n";
}
signed main(){
	freopen("seal.in","r",stdin);
	freopen("seal.out","w",stdout);
	int c=read(),t=read();
	while(t--)doing();
	return 0;
}

day2t3题解

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=6010;
const int mod=998244353;
int n,m,x[maxn],begid,tmax;
int is[maxn];

vector<int>tmp,V;
int s1[maxn],s2[maxn];
ll Ans=0;
int nxt[maxn][maxn];
int is_all_1[maxn];
vector<int>Vins[maxn];
// 把所有被 x[i] 删掉的元素放进 vins[i]
int Sta[maxn],top;
void init(){
    top=0;
    for(int i=1;i<=n+n;i++)Vins[i].clear();
    for(int i=begid+n;i>=begid;i--){
        while(top && x[i]>=x[Sta[top]]){
            Vins[i].push_back(Sta[top]);
            top--;
        }Sta[++top]=i;
    }
    memset(nxt[n+n],0,sizeof(nxt[n+n]));
    for(int i=n+n-1;i>=0;i--){
        memset(nxt[i],0,sizeof(nxt[i]));
        nxt[i][x[i+1]]=i+1;
        for(int j=x[i+1]+1;j<=m;j++)
            nxt[i][j]=nxt[i+1][j];
    }
    memset(is_all_1,0,sizeof(is_all_1));
    for(int i=n+1;i>=1;i--){
        is_all_1[i]=1;
        if(x[i-1]!=1)break;
    }
}
int getans(){
    // solve k=0 & 0opt
    V=tmp;
    sort(V.begin(),V.end());
    int sum=0;
    int len=V.size()-1;
    s1[1]=x[V[1]];
    for(int i=2;i<=len;i++)
        s1[i]=min(s1[i-1],x[V[i]]);
    s2[len]=x[V[len]];
    for(int i=len-1;i>=1;i--)
        s2[i]=min(s2[i+1],x[V[i]]);
    for(int i=1;i<=len;i++){
        int K=1e9;
        bool issame=True;
        for(int j=1;j<=i;j++)
            K=min(K,x[V[j]]-2);
        for(int j=i+1;j<=len;j++)
            K=min(K,x[V[j]]-1);
        K=max(K,0);
        sum+=K;
    }
    return sum;
}
namespace kge1{
    int y[maxn];
    ll num[maxn][2];
    ll delt[maxn][3];
    ll workL(){
        ll sum=0;
        ll val[3]={0};
        int L=begid,R=L+n-1;
        for(int S=1;S<=m;S++){
            val[0]=val[1]=val[2]=0;
            for(int i=L-1;i<=R+1;i++){
                num[i][0]=num[i][1]=0;
                delt[i][0]=delt[i][1]=delt[i][2]=0;
            }
            num[L-1][0]=1;
            for(int i=L-1;i<=R;i++){
                if(x[i]>=S+2){
                    num[i][0]+=val[0]-delt[i][0]+mod;
                    num[i][0]%=mod;
                }
                if(x[i]>=S+1){
                    num[i][1]+=val[0]-delt[i][1]+mod;
                    num[i][1]%=mod;
                }
                if(x[i]>=S+2 && i<=n){
                    num[i][1]+=val[2]-delt[i][2]+mod;
                    num[i][1]%=mod;
                }
                for(int x:Vins[i]){
                    delt[x][0]=val[0];
                    delt[x][1]=val[1];
                    delt[x][2]=val[2];
                }
                val[0]+=num[i][0];val[0]%=mod;
                val[1]+=num[i][1];val[1]%=mod;
                val[2]+=num[i][0];val[2]%=mod;
                if(nxt[i][tmax-1]==R+1){
                    sum+=num[i][1];
                    sum%=mod;
                }
            }
        }
        return sum;
    }
    ll workR(){
        ll sum=0;
        ll val[3]={0};
        int L=begid,R=L+n-1;
        for(int S=1;S<=m;S++){
            val[0]=val[1]=val[2]=0;
            for(int i=L-1;i<=R+1;i++){
                num[i][0]=num[i][1]=0;
                delt[i][0]=delt[i][1]=delt[i][2]=0;
            }
            num[L-1][0]=1;
            for(int i=L-1;i<=R;i++){
                if(x[i]>=S+1){
                    num[i][0]+=val[0]-delt[i][0]+mod;
                    num[i][0]%=mod;
                }
                if(x[i]>=S){
                    num[i][1]+=val[1]-delt[i][1]+mod;
                    num[i][1]%=mod;
                }
                if(x[i]>=S+1 && i>n){
                    num[i][1]+=val[2]-delt[i][2]+mod;
                    num[i][1]%=mod;
                }
                for(int x:Vins[i]){
                    delt[x][0]=val[0];
                    delt[x][1]=val[1];
                    delt[x][2]=val[2];
                }
                val[0]+=num[i][0];val[0]%=mod;
                val[1]+=num[i][1];val[1]%=mod;
                val[2]+=num[i][0];val[2]%=mod;
                if(nxt[i][tmax-1]==R+1){
                    sum+=num[i][1];
                    sum%=mod;
                }
            }
        }
        return sum;