Codeforces 1542E Abnormal Permutation Pairs-DP

传送门

题意

给定$n,mod$,求有多少对$(p,q)$满足:

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

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

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

答案对$mod$取模

$Case \ 1:n\leq 50$

$Case \ 2:n\leq 500$

Solution

Case 1

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

$$f[i][j]=\sum_{k=0}^{min(i-1,j)}f[i-1][j-k]$$

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

$$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]$$

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

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

总的方案数为$ans=\sum_{i=1}^nA_n^{i-1}*dp[n-i+1]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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]$表示长度为$i$的排列对$(p,q)$中,满足$inv(q)-inv(p)=j$的对数有多少个,转移时我们考虑把新的数$i$分别放入两个排列,对每种提供的差值分别有多少种放入方式,转移方程为$$f[i][j]=\sum_{k=-i+1}^{i-1}f[i-1][j-k]*(n-|k|)$$。

该方程乍一看还是$O(n^4)$的,但是通过观察,$f[i][j]$与$f[i][j-1]$的转移方程展开后是比较相似的,手动枚举几个例子可以发现$$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]$$

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

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

最终答案依然为$ans=\sum_{i=1}^nA_n^{i-1}*dp[n-i+1]$

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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);
}

作者

Fizzmy

发布于

2021-07-04

更新于

2021-07-04

许可协议

评论