传送门

题意

给定 n ， m o d n，mod n，mod，求有多少对 ( p , q ) (p,q) (p,q)满足：

1. p , q p,q p,q是长度为n的排列

2. p p p的字典序大于 q q q

3. p p p的逆序对数小于 q q q

答案对 m o d mod mod取模

C a s e   1 : n ≤ 50 Case \ 1:n\leq 50 Case 1:n≤50

C a s e   2 : n ≤ 500 Case \ 2:n\leq 500 Case 2:n≤500

Solution

Case 1

先考虑Case1，首先用 f [ i ] [ j ] f[i][j] f[i][j]表示满足在长度为i，有j个逆序对的排列的个数，可以通过一个简单的dp方程求出:

f [ i ] [ j ] = ∑ k = 0 m i n ( i − 1 , j ) f [ i − 1 ] [ j − k ] f[i][j]=\sum_{k=0}^{min(i-1,j)}f[i-1][j-k] f[i][j]=k=0∑min(i−1,j)​f[i−1][j−k]

然后我们考虑计算满足 p [ 1 ] > q [ 1 ] p[1]>q[1] p[1]>q[1]的所有合法的长度为 i i i的排列对数 d p [ i ] dp[i] dp[i]，令 p [ 1 ] = k , q [ 1 ] = j p[1]=k,q[1]=j p[1]=k,q[1]=j，则这一位产生的逆序对数， p p p产生了 k − 1 k-1 k−1个， q q q产生了 j − 1 j-1 j−1个。他们的差值为 k − j k-j k−j.因此我们对于每个 i i i枚举 j , k j,k j,k， p p p排列剩下 i − 1 i-1 i−1位的逆序对数 i n v ( p ) inv(p) inv(p)，由此可以推出满足条件的 q q q排列剩下 i − 1 i-1 i−1位的逆序对数区间，结合 f f f就可以算出 d p dp dp的值了，具体方程如下：

d p [ i ] = ∑ j = 1 i ∑ k = j + 1 i ∑ q = k − j + 1 i ∗ ( i − 1 ) 2 f [ i − 1 ] [ q ] ∗ ∑ p = 0 q − ( k − j + 1 ) f [ i − 1 ] [ p ] dp[i]=\sum_{j=1}^i\sum_{k=j+1}^i\sum_{q=k-j+1}^{\frac {i*(i-1)} 2}f[i-1][q]*\sum_{p=0}^{q-(k-j+1)}f[i-1][p] dp[i]=j=1∑i​k=j+1∑i​q=k−j+1∑2i∗(i−1)​​f[i−1][q]∗p=0∑q−(k−j+1)​f[i−1][p]

记录 f f f的前缀和，可以优化掉最后的 ∑ \sum ∑，这样用 O ( n 5 ) O(n^5) O(n5)的复杂度可以求出所有的 d p [ i ] dp[i] dp[i],改成枚举 k − j k-j k−j可以把复杂度降低为 O ( n 4 ) O(n^4) O(n4)

统计答案时，可以枚举 p , q p,q p,q中第一次出现不同数字的位置 i i i，这种情况的方案数为 A n i − 1 ∗ d p [ n − i + 1 ] A_n^{i-1}*dp[n-i+1] Ani−1​∗dp[n−i+1]，因为前 i − 1 i-1 i−1位可以随便排列。

总的方案数为 a n s = ∑ i = 1 n A n i − 1 ∗ d p [ n − i + 1 ] ans=\sum_{i=1}^nA_n^{i-1}*dp[n-i+1] ans=∑i=1n​Ani−1​∗dp[n−i+1]

代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,mod,mi[55]; 
int f[55][3000],sum[55][3000];
int dp[55];
int main()
{
	scanf("%d%d",&n,&mod);
	f[0][0]=1;sum[0][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=i*(i-1)/2;j++)
		{
			for (int k=0;k<i&&j-k>=0;k++)
				f[i][j]=(f[i][j]+f[i-1][j-k])%mod;
			if (j) sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
			else sum[i][j]=f[i][j];
		}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=i;j++)
			for (int k=j+1;k<=i;k++)
				for (int q=k-j+1;q<=i*(i-1)/2;q++)
					dp[i]=(dp[i]+1ll*f[i-1][q]*sum[i-1][q-(k-j+1)])%mod;
	}
	mi[0]=1;
	for (int i=1;i<=n;i++)
		mi[i]=1ll*mi[i-1]*(n-i+1)%mod;
	int ans=dp[1];
	for (int i=1;i<=n;i++)
		
		ans=(ans+1ll*mi[n-i]*dp[i])%mod;
	printf("%d",ans);
}

Case2

考虑上面算法的复杂度瓶颈在哪里，上述算法是通过计算单个排列的种种情况，然后枚举导致字典序不同的位置的数的差值，从而间接求出排列对的情况数，我们能不能跳过计算单个排列，直接计算排列对呢？答案是肯定的，令 f [ i ] [ j ] f[i][j] f[i][j]表示长度为 i i i的排列对 ( p , q ) (p,q) (p,q)中，满足 i n v ( q ) − i n v ( p ) = j inv(q)-inv(p)=j inv(q)−inv(p)=j的对数有多少个，转移时我们考虑把新的数 i i i分别放入两个排列，对每种提供的差值分别有多少种放入方式，转移方程为 f [ i ] [ j ] = ∑ k = − i + 1 i − 1 f [ i − 1 ] [ j − k ] ∗ ( n − ∣ k ∣ ) f[i][j]=\sum_{k=-i+1}^{i-1}f[i-1][j-k]*(n-|k|) f[i][j]=k=−i+1∑i−1​f[i−1][j−k]∗(n−∣k∣)。

该方程乍一看还是 O ( n 4 ) O(n^4) O(n4)的，但是通过观察， f [ i ] [ j ] f[i][j] f[i][j]与 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]的转移方程展开后是比较相似的，手动枚举几个例子可以发现 f [ i ] [ j ] = f [ i ] [ j − 1 ] − ( s u m [ i − 1 ] [ j − 1 ] − s u m [ i − 1 ] [ j − 1 − i ] + ( s [ i − 1 ] [ j − 1 + i ] − s [ i − 1 ] [ j − 1 ] ) ) , s u m [ i ] [ j ] = ∑ k ≤ j f [ i ] [ k ] f[i][j]=f[i][j-1]-(sum[i-1][j-1]-sum[i-1][j-1-i]+(s[i-1][j-1+i]-s[i-1][j-1])),sum[i][j]=\sum_{k\leq j}f[i][k] f[i][j]=f[i][j−1]−(sum[i−1][j−1]−sum[i−1][j−1−i]+(s[i−1][j−1+i]−s[i−1][j−1])),sum[i][j]=k≤j∑​f[i][k]

这样可以把复杂度降到 O ( n 3 ) O(n^3) O(n3)了

d p dp dp数组的求法和Case 1类似，具体为 d p [ i ] = ∑ j = 1 i ∑ k = j + 1 i s u m [ i − 1 ] [ − ( k − j + 1 ) ] dp[i]=\sum_{j=1}^i\sum_{k=j+1}^i sum[i-1][-(k-j+1)] dp[i]=j=1∑i​k=j+1∑i​sum[i−1][−(k−j+1)],仍然可以通过改成枚举 k − j k-j k−j降低复杂度。

最终答案依然为 a n s = ∑ i = 1 n A n i − 1 ∗ d p [ n − i + 1 ] ans=\sum_{i=1}^nA_n^{i-1}*dp[n-i+1] ans=∑i=1n​Ani−1​∗dp[n−i+1]

注意由于空间限制需要开滚动数组，同时转移状态中有负数，需要进行平移。

代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,mod,mi[550];
int T=130000;
int f[2][300000],sum[2][300000];
int dp[550];
int main()
{
	scanf("%d%d",&n,&mod);
	f[0][0+T]=1;sum[0][0+T]=1;
	for (int i=1;i<=10;i++) sum[0][i+T]=1;
	for (int i=1;i<=n;i++)
	{
		int ii=i&1;
		for (int j=-i*(i-1)/2;j<=i*(i-1)/2;j++)
		{
			f[ii][j+T]=(1ll*f[ii][j-1+T]-(1ll*sum[ii^1][j-1+T]-sum[ii^1][j-1-i+T])+(1ll*sum[ii^1][j-1+i+T]-sum[ii^1][j-1+T]))%mod;
			if (f[ii][j+T]<0) f[ii][j+T]+=mod;
		}
		for (int j=-i*(i-1)/2;j<=(i+1)*(i+2)/2;j++)
			sum[ii][j+T]=(sum[ii][j-1+T]+f[ii][j+T])%mod;
		for (int j=1;j<=i;j++)
			for (int k=j+1;k<=i;k++)
					dp[i]=(dp[i]+sum[ii^1][-(k-j+1)+T])%mod;
	}
	mi[0]=1;
	for (int i=1;i<=n;i++)
		mi[i]=1ll*mi[i-1]*(n-i+1)%mod;
	int ans=dp[1];
	for (int i=1;i<=n;i++)
		
		ans=(ans+1ll*mi[n-i]*dp[i])%mod;
	printf("%d",ans);
}