Warning: session_start(): open(/tmp/sess_adb7e95cfd431ee3ee2106bfad354a09, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/0/0a1fb0ef465f43d40a68985f0133c2ba.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Codeforces Round #729 (Div. 2) ======
[[https://codeforces.com/contest/1542|比赛链接]]
===== 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;
}