C++14(g++5.4) 解法, 执行用时: 70ms, 内存消耗: 3576K, 提交时间: 2019-12-20 21:56:33

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;

const int maxn = 2e5 + 5;
const int mod = 998244353;

int add(int x, int y) {
    if((x += y) >= mod) x -= mod;
    return x;
}

int mul(int x, int y) {
    LL z = (LL)x * y;
    return z - z / mod * mod;
}

int p[maxn], a[maxn], f[maxn], c[maxn];

void add(int x) {
    while(x > 0) {
        f[x]++;
        x -= x & (-x);
    }
}

int qry(int x) {
    int res = 0;
    while(x < maxn) {
        res += f[x];
        x += x & (-x);
    }
    return res;
}

int ff(int x) {
    if(c[x] != x) c[x] = ff(c[x]);
    return c[x];
}

int main() {
    p[0] = 1;
    for(int i = 1;i < maxn; ++i) p[i] = mul(p[i - 1], i);
    for(int i = 1;i < maxn; ++i) a[i] = add(p[i - 1], mul(a[i - 1], i));

    int n, x, ans = 0, pre = 0;
    scanf("%d", &n);
    for(int i = 1;i <= n; ++i) c[i] = i;
    for(int i = 1;i <= n; ++i) {
        scanf("%d", &x);
        int w = n - x - qry(x);
        //cout<<i<<" "<<ff(i)<<endl;
        if(ff(i) > x) ans = add(ans, p[n - i]);
        ans = add(ans, mul(pre, mul(p[n - i], w)));
        ans = add(ans, mul(a[n - i], w));
        add(x);
        if(ff(i) == x) pre++;
        else c[x] = i;
        //cout<<i<<" "<<ans<<endl;
    }
    cout << ans << endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 45ms, 内存消耗: 3556K, 提交时间: 2019-12-21 15:43:21

#include<algorithm>
#include<cstdio>
#define mxn 1000010
using namespace std;
const int mod=998244353;
int n,sl,fh,num,ans,a[mxn],f[mxn],tr[mxn],fa[mxn],fac[mxn],ifc[mxn];
int rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
void upd(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
void upd(int i) {for(;i<=n;i+=(i&-i)) tr[i]++;}
int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
int getfa(int x)
{
	if(fa[x]!=x) fa[x]=getfa(fa[x]);
	return fa[x];
}
int main()
{
	n=rd();fac[0]=1;
	for(int i=1;i<=n;++i) fa[i]=i,fac[i]=1ll*i*fac[i-1]%mod,f[i]=(fac[i-1]+1ll*i*f[i-1])%mod;
	for(int x,c,i=1;i<=n;++i)
	{
		x=rd();c=n-x-i+1+qry(x);upd(x);
		ans=(ans+1ll*c*f[n-i]+1ll*c*num%mod*fac[n-i])%mod;
		if(getfa(i)>x) upd(ans,fac[n-i]);
		if(getfa(i)==x) num++; else fa[x]=i;
	}
	printf("%d\n",ans);
	return 0;
}