CF1542E2

首先复杂度肯定是三方对吧。

先对付字典序的限制。那就枚举相等前缀的长度呗。然后下一位 (p) 要比 (q) 小。

然后考虑逆序对。发现相等前缀内部的逆序对，以及相等前缀与后面的后缀产生的逆序对，(p) 和 (q) 是相等的！于是就看后面了啊。以及前面和后面完完全全是独立的，就是说你完全可以把前面和后面看作两个独立的排列，然后以组合数方案数合并起来的每一种情况都是等价的（这大概是各种排列题的套路想法之一吧）。同时前缀是什么样根本不重要，于是需要考虑后缀的排列，设前缀长度为 (x)（之后抛弃这个假设），方案数乘上 (mathrm A_n^x)（模数不是质数，不能用逆元。我是预处理组合数，然后 (mathrm A_n^x=dbinom nxx!)）累到答案里。

考虑对长度为 (x=1sim n) 后缀怎么操作呢。容易想到枚举 (p) 和 (q) 在第一位的值（那么第一位与后面产生的逆序对数就定下来了），然后设长度为 (n-1) 的逆序对数为 (i) 的排列数量为 (f_i)，那么贡献就是需要枚举 (p) 和 (q) 后 (n-1) 位分别的逆序对数使得总逆序对是 (p) 比 (q) 大的，乘起来累起来（此处又用到了将排列劈成两半（此处是 (1) 和 (2sim n)）之后独立开来的想法）。

那么对于每个 (x)，这个 (f) 数组显然可以从左往右 D 一 DP。具体就是 (dp_{i,j}) 表示长度为 (i) 的逆序对数为 (j) 的排列数量，枚举最后一位然后把前面 (i-1) 位独立开来显然有 (dp_{i,j}=sumlimits_{k=1}^idp_{i-1,j-(i-k)})。(i) 是线性的，然而 (j) 是平方，暴力转移是四方的，前缀和优化一下即可。

下面重点来了：知道了 (f) 数组怎么求对某个 (x) 的贡献呢（根据直觉 (x) 们是不可能合起来计算的）。列出式子

[ans=sumlimits_{p=1}^xsumlimits_{q=p+1}^xsumlimits_{i=q-p+1}^{x^2}f_isumlimits_{j=0}^{i-(q-p+1)}f_j ]

注意到后面两个 (sum) 只跟 (q-p+1) 有关，所以我们可以线性枚举这玩意 instead of 平方枚举 (p,q)。以及最后一个 (sum) 可以写成前缀和（前缀和可以预处理呀）。

[ans=sumlimits_{d=2}^x(x-d+1)sumlimits_{i=d}^{x^2}f_iF_{i-d} ]

现在直接算是三方的，加上枚举 (x) 总复杂度是四方的，不行。想办法把计算这个和式优化到两方。先固定第一个 (sum)，看右边的那个东西能不能线性或者均摊线性算出来。然后仔细一看就傻眼了……这个就是把 (F) 倒过来的卷积呀……(500^3) 根本不允许再带一个 log，况且我也不会 FFT。那就没办法了，只能让第一个 (sum) 参与优化，交换和式：

[ans=sum_{i=2}^{x^2}f_isum_{d=2}^{min(x,i)}(x-d+1)F_{i-d} ]

考虑的是把后面这个 (sum) 优化到常数或均摊常数。(x+1) 以及 (d) 前面的负号先去掉，因为这肯定不能成为难度的瓶颈。于是要求 (sumlimits_{d=2}^{min(x,i)}dF_{i-d})。你可能会说这不还是卷积嘛！但是这个卷积的左元 (d) 是个很简单的东西，可化解的。考虑递推，你考虑将 (i=i_0-1) 和 (i=i_0) 时候的这个和式做差，将 (F) 下标相同的项对齐，系数减出来恰好都为 (1) 好吧！也就是说按 (i) 从小到大的顺序，只需要再预处理一个 (F) 的前缀和（(mathcal F) 或者 (mathbb F)，滑稽），就可以实现 (mathrm O(1)) 的递推了（一些边角就也常数处理一下吧，挺烦）。

总复杂度三方。顺带说一嘴，DP 数组如果开三方数组的话会 MLE，那只能滚动，这样就只能即时贡献答案。

code（不算好写，但也不算难写）

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,mod;
int fact[N],comb[N][N];
int dp[2][N*N],Dp[2][N*N];
int FF[N*N];
int ans;
int A(int x,int y){return 1ll*comb[x][y]*fact[y]%mod;}
int rmd(int x){
	x>=mod&&(x-=mod);
	x<=-mod&&(x+=mod);
	return x;
}
void mol(int &x){
	x>=mod&&(x-=mod);
	x<=-mod&&(x+=mod);
}
void deal(int x){
	#define f dp[n-x-1&1]
	#define F Dp[n-x-1&1]
	for(int i=0;i<=n*(n-1)/2;i++)FF[i]=rmd((i?FF[i-1]:0)+F[i]);
	int now=0,sum=0;
	for(int i=2;i<=n*(n-1)/2;i++){
		if(i==2)now=1ll*(n-x-i+0+1)*F[0]%mod;
		else{
			if(i-n+x>0)mol(now-=1ll*(n-x-(i-1)+(i-1-n+x)+1)*F[i-1-n+x]%mod);
			mol(now+=1ll*(n-x-i+(i-2)+1)*F[i-2]%mod);
			int l=max(0,i-n+x),r=i-3;
			if(l<=r)mol(now-=rmd(FF[r]-(l?FF[l-1]:0)));
		}
		mol(sum+=1ll*f[i]*now%mod);
	}
	mol(ans+=1ll*sum*A(n,x)%mod);
}
int main(){
	cin>>n>>mod;
	fact[0]=1;for(int i=1;i<=n;i++)fact[i]=1ll*fact[i-1]*i%mod;
	comb[0][0]=1;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)comb[i][j]=((j?comb[i-1][j-1]:0)+comb[i-1][j])%mod;
	dp[0][0]=1;
	for(int i=0;i<=n*(n-1)/2;i++)Dp[0][i]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n*(n-1)/2;j++){
			int l=max(0,j-(i-1)),r=j;
			dp[i&1][j]=rmd(Dp[i-1&1][r]-(l?Dp[i-1&1][l-1]:0));
			Dp[i&1][j]=rmd((j?Dp[i&1][j-1]:0)+dp[i&1][j]);
		}
		if(i<n)deal(n-1-i);
	}
	cout<<(ans+mod)%mod;
	return 0;
}