目录

Codeforces Round #729 (Div. 2)

比赛链接

E. Abnormal Permutation Pairs

题意

问有多少对 $1\sim n$ 的排列 $(p,q)$ 满足 $p$ 字典序小于 $q$ 逆序对个数大于 $q$，结果需要取模但不保证模是素数。

题解

考虑枚举 $x$ 使得 $p[1\sim x]=q[1\sim x],p[x+1]\neq q[x+1]$。

记 $\text{inv}(p)$ 表示 $p$ 中的逆序对。于是此时等价于询问有多少对 $1\sim n-x$ 的排列 $(p,q)$ 满足 $p[1]\lt q[1]$，$\text{inv}(p)\gt \text{inv}(q)$。

然后枚举 $y=q[1]-p[1]$，于是问题转化为有多少对 $1\sim n-x-1$ 的排列 $(p,q)$ 满足 $\text{inv}(p)\gt \text{inv}(q)+y$。

设 $p_i$ 表示元素 $i$ 在 $p$ 中的逆序数，于是有 $0\le p_i\lt i-1$，问题转化为 $\sum p_i\gt \sum q_i+y$。

设 $f(i,j)$ 表示 $\sum_{k=1}^{i+1}p_k-q_k=j$ 的方案数，枚举 $t=p_k-q_k$，于是又有

$$ f(i-1,j)\to (i+1-t)f(i,j+t)(-i\le t\le i) $$

发现可以二维差分维护，于是状态转移复杂度 $O(1)$，时间复杂度 $O(n^3)$。

最后答案为

$$ \sum_{i=0}^{n-2}A_{n}^i\sum_{j=1}^{n-i-1}(n-i-j)\sum_{k\gt j}f(n-i-2,k) $$

查看代码

查看代码 

const int MAXN=505,MAXV=MAXN*MAXN/2,MAXT=MAXV+1e3;
int p[MAXN][MAXV<<1|1],frac[MAXN];
LL temp[MAXT<<1|1],temp2[MAXT<<1|1];
int main()
{
	int n=read_int(),mod=read_int();
	p[0][MAXV]=1;
	frac[0]=1;
	_rep(i,1,n){
		frac[i]=1LL*frac[i-1]*(n-i+1)%mod;
		mem(temp,0);
		_rep(j,-MAXV,MAXV){
			temp[j-i+MAXT]=temp[j-i+MAXT]+p[i-1][j+MAXV];
			temp[j+1+MAXT]=temp[j+1+MAXT]-(p[i-1][j+MAXV]<<1)+(mod<<1);
			temp[j+i+2+MAXT]=temp[j+i+2+MAXT]+p[i-1][j+MAXV];
		}
		_rep(j,1,MAXT<<1){
			temp[j]=(temp[j-1]+temp[j])%mod;
			temp2[j]=temp[j]+temp2[j-1];
		}
		_rep(j,-MAXV,MAXV)
		p[i][j+MAXV]=temp2[j+MAXT]%mod;
	}
	_rep(i,0,n){
		for(int j=2*MAXV;j>MAXV;j--)
		p[i][j-1]=(p[i][j]+p[i][j-1])%mod;
	}
	int ans=0;
	_for(i,0,n-1){
		_for(j,1,n-i)
		ans=(ans+1LL*frac[i]*(n-i-j)%mod*p[n-i-2][j+1+MAXV])%mod;
	}
	enter(ans);
	return 0;
}