题目分析

暂时不考虑必须严格大于给定排列的问题。
首先发现,如果序列中存在长度$\geq 3$的下降序列的话,一定是不合法的。因为这样一个下降序列中间那个元素,会经过一次往左走的交换和一次往右走的交换,一定有一次离其目标位置远了,也就是走了一个无效步,不能达到下界。
这个条件可以转化为,原序列能被拆成两个上升序列。
进行dp,考虑$f(i,j)$表示还有$i$个元素没放,其中$j$个是比放了的元素更大的,这$j$个元素我们称之为牛逼元素,然后将这些元素放完,有多少种方法。发现因为牛逼元素比较牛逼,所以随便放一个牛逼元素都是合法的,而如果放其他元素的话,只能放最小的那个,不然一定会出现第三个上升序列。
得到dp方程:$f(i,j)=\sum_{k=0}^j f(i-1,j-k)$
显然$f(i,j)=f(i-1,j)+f(i,j-1)$
打表找规律,发现$f(i,j)=C_{i+j-1}^j-C_{i+j-1}^{j-2}$,这个可以用数学归纳法证一波。于是在预处理阶乘和阶乘的逆元后,这东西就能$O(1)$求了。
接下来开始考虑严格大于给定排列的限制。
设当前考虑到排列的第$i$个元素的放法,并且前$i-1$位放的元素和给定的排列里的元素一毛一样。设给出的排列这一位是$a_i$,其后有$b_i$个元素大于$a_i$,有$c_i$个元素小于$a_i$。$b_i$和$c_i$可以用树状数组求。
如果这一位放的元素大于$a_i$,那么以后的位置不再受严格大于给定排列这个条件的限制,我们可以统一求一波。设当前这种情况下,还存在$bg$个严格大于前$i$个$a$的元素,那么前$i$位与$a$相同后面不同的合法排列数就是:$\sum_{j=0}^{bg-1}f(n-i,j)=f(n-i+1,bg-1)$。当然啦,如果$bg=0$,后面一定是从小到大放元素,一定是在取这种前缀条件下的最小排列,一定不是严格大于$a$的排列,可以直接结束计算。
如果这一位放$a_i$的话,检验一下$a_i$是否是前面放法和$a$相同条件下的牛逼元素或其他元素中最小的那个,不是就直接结束计算。
复杂度$O(nlogn)$,瓶颈在树状数组。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=600005,mod=998244353;
int T,n,ans,a[N],b[N],c[N],s[N],fac[N<<1],ni[N<<1];
int qm(int x) {return x>=mod?x-mod:x;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
int lowbit(int x) {return x&(-x);}
void add(int x) {while(x<=n) ++s[x],x+=lowbit(x);}
int query(int x) {int re=0;while(x) re+=s[x],x-=lowbit(x); return re;}
int C(int d,int u) {return 1LL*fac[d]*ni[u]%mod*ni[d-u]%mod;}
int getf(int i,int j) {
    if(j==0) return 1;
    if(j==1) return i;
    return qm(C(i+j-1,j)-C(i+j-1,j-2)+mod);
}
int main()
{
    T=read();
    fac[0]=1;for(RI i=1;i<=1200000;++i) fac[i]=1LL*fac[i-1]*i%mod;
    ni[1200000]=ksm(fac[1200000],mod-2);
    for(RI i=1199999;i>=0;--i) ni[i]=1LL*ni[i+1]*(i+1)%mod;
    while(T--) {
        n=read();
        for(RI i=1;i<=n;++i) a[i]=read(),s[i]=0;
        for(RI i=n;i>=1;--i)
            c[i]=query(a[i]),add(a[i]),b[i]=n-i-c[i];
        int flag,bg=n;ans=0;
        for(RI i=1;i<=n;++i) {
            if(b[i]<bg) bg=b[i],flag=1;
            else flag=0;
            if(!bg) break;
            ans=qm(ans+getf(n-i+1,bg-1));
            if(!flag&&b[i]<n-i) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *