[NOI2018]冒泡排序

C++14(g++5.4) 解法, 执行用时: 190ms, 内存消耗: 23776K, 提交时间: 2020-09-21 08:39:52

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1200000+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int fac[N],ifac[N];
void init(int n) {
    fac[0]=1;
    for (int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m) {
    if (n<m) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int S(int n,int m) {
    if (n<m) return 0;
    return (C(n+n-m,n-m)-C(n+n-m,n-m-1)+mod)%mod;
}

int n,p[N],pre[N],suf[N],cnt[N];

int c[N];
void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]+=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    init(1200000);
    int T=read();
    while (T--) {
        memset(c,0,sizeof(c));
        n=read();
        for (int i=1;i<=n;++i) p[i]=read();
        pre[1]=p[1],suf[n]=p[n];
        for (int i=2;i<=n;++i) pre[i]=max(pre[i-1],p[i]);
        for (int i=n-1;i>0;--i) suf[i]=min(suf[i+1],p[i]);
        for (int i=n;i;--i) add(p[i],1),cnt[i]=sum(pre[i]);
        int ans=0;
        for (int i=1,mx2=0;i<n;++i) {
            if (mx2>suf[i]) break;
            ans=(ans+S(n-i+1,cnt[i]+1))%mod;
            if (p[i]<pre[i]) mx2=max(mx2,p[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 136ms, 内存消耗: 23848K, 提交时间: 2022-08-24 09:38:58

#include<bits/stdc++.h>
#define ll long long
#define N 600005

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=998244353;
ll ksm(ll t,ll x) {
	ll ans=1;
	for(;x;x>>=1,t=t*t%mod)
		if(x&1) ans=ans*t%mod;
	return ans;
}
int n;
int q[N];
ll fac[N*2],ifac[N*2];
void pre(int n) {
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	ifac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}

ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
ll cal(int n,int k) {
	if(k==0) return 1;
	if(k==1) return n;
	return (C(n+k,k)-C(n+k,k-1)+mod)%mod;
}
int low(int i) {return i&(-i);}
int tem[N];
void add(int v,int f) {for(int i=v;i<=n;i+=low(i)) tem[i]+=f;}
int query(int v) {
	int ans=0;
	for(int i=v;i;i-=low(i)) ans+=tem[i];
	return ans;
}

bool vis[N];
int main() {
	pre(1200000);
	int T=Get();
	while(T--) {
		ll ans=0;
		n=Get();
		for(int i=1;i<=n;i++) tem[i]=0;
		for(int i=1;i<=n;i++) q[i]=Get();
		int mx=0,cnt; 
		for(int i=1;i<=n;i++) {
			if(q[i]>mx) {
				mx=q[i];
				cnt=n-q[i]-(i-1-query(q[i]-1));
			}
			(ans+=cal(n-i+1,cnt-1))%=mod;
			int low=query(q[i]-1);
			if(low!=i-1&&low!=q[i]-1) break;
			add(q[i],1);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

详情