C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 480K, 提交时间: 2019-09-20 20:30:34

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 998244353
int f[1005],g[1005],h[1005],a[1005],b[1005],c[1005],t,n,i,j,ans;
int main()
{
    scanf("%d",&t);
    for(i=1;i<1005;i++)b[i]=b[i-1]+i;
    for(f[0]=1,i=2;i<1005;i++)f[i]=(ll)(i-1)*(f[i-1]+f[i-2])%P;
    for(i=1;i<1005;i++)g[i]=(f[i-1]+(ll)(i-1)*g[i-1])%P;
    for(i=2;i<1005;i++)h[i]=(2LL*g[i-1]+(ll)(i-2)*h[i-1])%P;
    for(i=1;i<1005;i++)c[i]=c[i-1]+i*i;
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)scanf("%d",a+i);
        if(n==1)
        {
            puts("0");
            continue;
        }
        ans=(ll)(n-1)*n*(n+1)%P*(P+1)/6%P;
        ans=(ll)ans*ans%P*h[n-2]%P;
        for(i=1;i<=n;i++)ans=(ans+(ll)(P-h[n-2]+g[n-2])*b[i-1]%P*b[a[i]-1]+(ll)(P-h[n-2]+g[n-2])*b[n-i]%P*b[n-a[i]]+(ll)(P-h[n-2])*b[i-1]%P*b[n-a[i]]%P+(ll)(P-h[n-2])*b[n-i]%P*b[a[i]-1])%P;
        for(i=1;i<n;i++)for(j=i+1;j<=n;j++)
        {
            if(a[i]<a[j])ans=(ans+((ll)(P-2)*g[n-2]+f[n-2])%P*(j-i)*(a[j]-a[i]))%P;
            ans=(ans+(ll)max(a[j]-a[i],a[i]-a[j])*(j-i)*h[n-2])%P;
        }
        cout<<ans<<endl;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 73ms, 内存消耗: 616K, 提交时间: 2019-09-20 19:46:10

#include<bits/stdc++.h>
#define fo(i,a,b)for(int i=a,_e=b;i<=_e;i++)
#define ll long long
using namespace std;
const int N=5e3+5,mo=998244353;
int n,p[N];
ll f[N],f1[N],f2[N],all,ans,s1,s2,s3,s4;
int T;
int main(){
	for(cin>>T;T--;){
		scanf("%d",&n);f[0]=1;
		ans=0;all=0;
		fo(i,1,n)
			scanf("%d",&p[i]),f[i]=(f[i-1]+(i>1?f[i-2]:0))*(i-1)%mo,
			f1[i]=(f[i]+f[i-1])%mo,f2[i]=(i>2?f[i-2]+f[i-1]*2+f[i]:0)%mo,all=(all+((ll)i*(i-1)>>1))%mo;
		fo(i,1,n)fo(j,i+1,n){
			if(p[i]>p[j]){
				s1=((ll)p[j]*(p[j]-1)>>1)%mo;
				s2=((ll)(n-p[i]+1)*(n-p[i])>>1)%mo;
				s3=(((ll)(n-p[j]+1)*(n-p[j])+(ll)p[i]*(p[i]-1)>>1)-(p[i]-p[j]))%mo;
				ans=(ans+((s1+s2)*f1[n-2]+(all-s1-s2-s3)*f2[n-2])%mo*(j-i))%mo;
			}else{
				s1=((ll)p[j]*(p[j]-1)>>1)%mo;
				s2=((ll)(n-p[i]+1)*(n-p[i])>>1)%mo;
				s3=((ll)(n-p[j]+1)*(n-p[j])+(ll)p[i]*(p[i]-1)>>1)%mo;
				ans=(ans+((all-s1-s2-s3+(p[j]-p[i]))*f2[n-2]+(s1+s2-2*(p[j]-p[i]))*f1[n-2]+
					(p[j]-p[i])*f[n-2])%mo*(j-i))%mo;
			}
		}
		printf("%lld\n",(ans+mo)%mo);
	}
		
}