[noi2018] bubble sort (combination + Cartland number +dp+ tree array)

Rogue portal

8pts

n! Enumerate permutations , Then judge

44pts

First, consider what kind of sequence is qualified
The title prompt inspires us , Consider the movement of each element
Because the total number of exchanges is to reach the lower bound , So every exchange must be beneficial
Consider if the order is No i A place is p[i]
if $p[i]=i$, Then this position cannot be exchanged
if $p[i]<i$, Then this number needs to move to the left , And cannot move to the right
Then there can't be one j Satisfy ,$j>i,p[j]<p[i]$, Otherwise, the two positions will be exchanged once , that $p[i]$ It moves in the opposite direction , The answer is bound to get bigger , namely $i$ The numbers on the right are better than $p[i]$ Big
if $p[i]>i$, Similar can be obtained i The numbers on the left are better than $p[i]$ Small
And these three restrictions are equivalent to the original restrictions
Directly press and select those numbers
The limitation of dictionary order can be similar to digits dp Go ahead
Complexity $O(2^{n}n)$

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5+7;
typedef long long LL;
const int mod = 998244353;
int n,a[N];
LL f[1<<20][2];
void solve()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	int m=(1<<n);
	memset(f,0,sizeof(f));
	f[0][1]=1;
	for(int s=0;s<m-1;s++) {
       int p=0; int a1=0,a2=n+1; for(int i=1;i<=n;i++) if((s>>(i-1))&1)
		{
    
			p++;
			a1=max(a1,i);
		}
		else a2=min(a2,i);
		p++;
		for(int limit=0;limit<=1;limit++) {
       int up=(limit?a[p]:1); for(int i=up;i<=n;i++) {
       int k=(limit&&(i==up)); if(!((s>>(i-1))&1))
				{
    
					if(i>=p)
					{
    
						if(a1<i)
						f[s+(1<<(i-1))][k]=(f[s+(1<<(i-1))][k]+f[s][limit])%mod;
					}
					else
					{
    
						if(i<=a2)
						f[s+(1<<(i-1))][k]=(f[s+(1<<(i-1))][k]+f[s][limit])%mod;
					}
				}
			}
		}
	}
	printf("%lld\n",f[m-1][0]);
}
int main()
{
    
	int T;
	cin>>T;
	while(T--)
	{
    
		solve();
	}
	return 0;
}

80pts

An important conclusion ：
Do not consider dictionary order restrictions
The question is equivalent to how many permutations , Satisfy that there is no length greater than or equal to 3 Descending subsequence of

The need for ：

That is, if the arrangement is legal , Then there is no length greater than or equal to 3 Descending subsequence of
If not , There are three numbers $i,j,k$ Satisfy ,$i<j<k,p[i]>p[j]>p[k]$
if $j<p[j]$, As can be seen from the above ,j The numbers on the left are better than j Small , And $p[i]>p[i]$ contradiction
if $j>p[j]$, be j The numbers on the right are better than j Big , And $p[j]>p[k]$ contradiction
So contradiction , That is, the original proposition holds
adequacy

That is, if it does not exist $p[i]>p[j]>p[k]$, Then the nature is established
Consider an exchange , Exchanged $p[i],p[i+1]$
Then we can know from the question ,$p[i]>p[i+1]$
And because there is no length greater than or equal to 3 Descending subsequence of , therefore i The numbers on the left are less than $p[i]$
Then there is $p[1\dots \dots i-1]$ and $p[i+1]$ in total i The number ratio is $p[i]$ Small , namely $p[i]>i$
Similarly, we can get $p[i+1]<i+1$, Then this exchange is legal for the final arrangement
So the proposition holds
That is, the question is equivalent to finding how many permutations , Satisfy that there is no length greater than or equal to 3 Descending subsequence of

consider dp
set up $dp[i][j]$ Indicates how many are of length i Permutation , Satisfying the first element is j, And there is no length greater than or equal to 3 Descending subsequence of , By definition $j\le i$
Consider the second number k
if $j<=k$, Then add dp[i-1][k], The reason why this is equal to j, Without repeating , Because although the whole sequence is an arrangement , But each sub segment is not an arrangement , And the reason why we can transfer , Because we only consider the relative relationship of elements , That is, the value after discretization , So the length is i Sequence of numbers , The length is i-1 Sequence of numbers , It is obviously possible to have equal values after discretization
if $1<k<j$, Then there must be one $j,k,1$ Illegal , Descending subsequence , Therefore, the contribution is 0
if $k==1$
Contribution is obviously not $dp[i-1][1]$
First 1~j-1 It must be in ascending order , Otherwise, there will be illegal descending subsequences
If it's not legal , There is $x<y,j>p[x]>p[y]>1$
Consider a mapping ：
hold x Move to x+1 Location , Special let j-1 Move to 1 Location
Then the new sequence and the original sequence are one-to-one corresponding , That is, a double shot
And there are $(j-1,p[x]-1,p[y]-1)$ Descending subsequence of
So if you fill in k be equal to 1, Is equivalent to nonexistence with j-1 The starting length is 3 Descending subsequence of , namely dp[i-1][j-1]
Combine the three situations
$dp[i][j]={\sum }_{k=j-1}^{i-1}dp[i-1][k]$

Consider the limitations of dictionary order
Enumeration and the longest common prefix of a given permutation i
Set the maximum prefix to x, Satisfy $p[j]<=x,j>=i$ Of j The number of s
Then after discretization ,x Namely s
And because of the limitation of dictionary order , So the number should be >p[i], in other words , The minimum number that can be filled in the current position is s+1, The biggest thing is n-i+1, Of course, after discretization
The answer is
$$Ans=\sum _{i=1}^{n-1}\sum _{k=s+1}^{n-i+1}dp[n-i+1][k]$$
Preprocessing dp value , Through prefix and optimization , Complexity $O(n^2)$
Because the code is simple , So a little

100pts

Observe that the answer is actually several dp Array suffixes and
set up $s(n,m)={\sum }_{i=m}^{n}dp[n][i]$, among $m\le n$
be
$$s(n,m)=\sum _{i=m+1}^{n}dp[n][i]+dp[n][m]$$
$$=\sum _{i=m+1}^{n}dp[n][i]+\sum _{i=m-1}^{n-1}dp[n-1][i]$$
$$=s(n,m+1)+s(n-1,m-1)$$
Consider the meaning of combination ,
In the plane rectangular coordinate system, from $(0,0)$ Go to the $(n,m)$ The number of plans to take one step down or one step up right at a time
And not more than $y=x$ This line and x Under the axis
First of all, only through these two ways , Go anywhere , It's impossible to cross $y=x$, But it is possible to cross x Axis
Because only the second kind will take a step to the right , So there is n The second operation , You can also get n-m The first operation
To make these two operations similar , Think about it , Change to right
Then I went to (n,m), The new operation will go to (2n-m,m), Because I walked to the right more n-m Time
namely , Take one step up or down the right every time , Go to the (2n-m,m) Number of alternatives , And not more than x Axis
This is also a double shot with the original problem
Because it can't be more than x Axis , So in every prefix , The number of times to go up should be greater than or equal to the number of times to go down
This is the variation of Cartland number , The number of programmes is $s(n,m)=C_{2n-m}^{n-m}-C_{2n-m}^{n-m-1}$
$$Ans=\sum _{i=1}^{n-1}s(n-i+1,s+1)$$
Number of pretreatment combinations , Use a tree array to find s
Complexity $O(n\log n)$

#include<bits/stdc++.h>
using namespace std;
const int N = 6e5+7;
typedef long long LL;
const int mod = 998244353;
int c[N];
int n;
void add(int x,int v)
{
    
	for(int i=x;i<=n;i+=i&-i)
	c[i]+=v;
}
int ask(int x)
{
    
	int res=0;
	for(int i=x;i;i-=i&-i)
	res+=c[i];
	return res;
}
int a[N];
LL fac[N*2],inv[N*2];
LL M = N*2-2;
LL Pow(LL a,LL b)
{
    
	LL res=1;
	while(b)
	{
    
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int pre[N],suf[N];
int leq[N];
LL C(int n,int m)
{
    
	if(n<m) return 0;
	return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
LL S(int n,int m)
{
    
	return (C(2*n-m,n-m)-C(2*n-m,n-m-1)+mod)%mod;
}
void solve()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	pre[i]=max(pre[i-1],a[i]);
	suf[n+1]=n+1;
	for(int i=n;i>=1;i--)
	suf[i]=min(suf[i+1],a[i]);
	for(int i=n;i>=1;i--)
	{
    
		add(a[i],1);
		leq[i]=ask(pre[i]);
	} 
	for(int i=1;i<=n;i++)
	add(a[i],-1);
	int Max=0;
	LL ans=0;
	for(int i=1;i<=n;i++)
	{
    
		if(Max>suf[i]) break;
		if(leq[i]+1<=n-i+1)
		ans=(ans+S(n-i+1,leq[i]+1))%mod;
		if(a[i]<pre[i]) Max=max(Max,a[i]);
	}
	printf("%lld\n",ans);
}
int main()
{
    
	int T;
	cin>>T;
	fac[0]=1;
	for(int i=1;i<=M;i++)
	fac[i]=(LL)fac[i-1]*i%mod;
	inv[M]=Pow(fac[M],mod-2);
	for(int i=M-1;i>=0;i--)
	inv[i]=(LL)inv[i+1]*(i+1)%mod;
	while(T--)
	{
    
		solve();
	}
	return 0;
}