代码

#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
#define SZ 999999
int T,n,s[SZ],q[SZ],f[1003][2][2003];
void sol()
{
    memset(f,0,sizeof f);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",q+i);
    for(int i=1;i<=n;++i)
    {
        s[i]=0;
        for(int j=i+1;j<=n;++j)
            s[i]+=q[j]<q[i];
    }
    int G=n+n;
    for(int i=0;i<=G;++i)
        f[0][0][i]=1;
    for(int i=1;i<=n;++i)
    {
    for(int g=0;g<2;++g)
    {
        for(int j=0;j<=n-i;++j)
        {
            if(g==0&&j<s[i]) continue;
            if(j==0)
            {
                for(int t=0;t<=G;++t)
                {
                    (f[i][g||(j>s[i])][t]+=f[i-1][g][t])%=MOD;
                    if(t) (f[i][g||(j>s[i])][t]-=f[i-1][g][t-1])%=MOD;
                }
            }
            else
                (f[i][g||(j>s[i])][i+j]+=f[i-1][g][i+j-1])%=MOD;
        }
    }
    for(int g=0;g<2;++g)
        for(int j=1;j<=G;++j)
            (f[i][g][j]+=f[i][g][j-1])%=MOD;
    }
    int ans=f[n][1][G];
    ans=(ans%MOD+MOD)%MOD;
    printf("%d\n",ans);
}
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
int main()
{
    scanf("%d",&T);
    while(T--) sol();
}

评测结果