P4769 [NOI2018] Bubble Sort (Combinatorics)

前言

Here is the linear approach.
The nature of a few words in the solution to the problem was stunned for a whole morning.
too vegetable

解析

Consider what permutations are not legal.
A permutation if invalid,That is, during a certain exchange, the distance of one of the elements from the target does not decrease but increases,Then this number will be changed again in the future,That is, the number will jump repeatedly.
Consider how many numbers will hop over and over again,不难发现,Jumps repeatedly,It is equivalent to having an element on the left that is larger than itself,There are elements on the right that are smaller than itself,That is, there is a decreasing subsequence of length three.
Therefore, the necessary and sufficient conditions for legality can be abstracted：There are no decreasing subsequences of length three,也就等价于The permutation can be split into two increasing sequences.

这咋算啊？
hit the table,When it is found that there is no lexicographical order,The answer is the Cattelan number.
为什么呢？
Try to go up the um set.设 $m{x}_i={\max }_{j=1}^i{a}_j$,Then a permutation can be understood as all $(m{x}_i,i)$ A path where the points are connected sequentially,It is not difficult to find that it is called the Cattelan number“ $(0,0)->(n,n)$ and not more than the diagonal” The path is bijective.

Then this question is fine,Violently enumerates the first position larger than the given permutation,Then it must be updated at this time $m{x}_i$,设 $f((a,b)->(c,d))$ 是从 $(a,b)$ 走到 $(c,d)$ and does not exceed the number of diagonal solutions（It can be tolerated and rejected by turning over $O(1)$ 求解）,So here's the number of options ${\sum }_{j=m{x}_i+1}^{n}f((j,i)->(n,n))=f((m{x}_i+1,i-1)->(n,n))$.Until the prefix of the given permutation must not be split into two increasing sequences is exit.
总复杂度 $O(n)$.

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("line: %d\n",__LINE__)

inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}
bool mem1;

const int N=2e6+100;
const int inf=1e9+100;
const int mod=998244353;
const bool Flag=0;

#define add(x,y) ((((x)+=(y))>=mod)&&((x)-=mod))
inline ll ksm(ll x,ll k){
    
  ll res(1);
  while(k){
    
    if(k&1) res=res*x%mod;
    x=x*x%mod;
    k>>=1;
  }
  return res;
}

int n;

int a[N];
ll jc[N],ni[N];
void init(int n){
    
  jc[0]=1;
  for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
  ni[n]=ksm(jc[n],mod-2);
  for(int i=n-1;i>=0;i--) ni[i]=ni[i+1]*(i+1)%mod;
}
inline int C(int n,int m){
    
  return n<m||m<0?0:jc[n]*ni[m]%mod*ni[n-m]%mod;
}

inline int walk(int i,int j){
    
  return (C(n-i+n-j,n-i)+mod-C(n-1-i+n+1-j,n-1-i))%mod;
}
bool vis[N];
void work(){
    
  n=read();
  for(int i=1;i<=n;i++) a[i]=read(),vis[i]=0;
  int mx(0),sec(1);
  int ans(0);
  for(int i=1;i<=n;i++){
    
    vis[a[i]]=1;
    if(a[i]>mx) mx=a[i];
    else if(a[i]!=sec){
    
      add(ans,walk(mx+1,i-1));
      break;
    }
    while(vis[sec]) ++sec;

    add(ans,walk(mx+1,i-1));
  }
  printf("%lld\n",ans);
}

bool mem2;
signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  init(2e6);
  int T=read();
  while(T--) work();
  return 0;
}