题目大意
定义两个长度为$n$的排列A与B相似，若$\forall i$，满足$C(A,A_i)=C(B,B_i)$。其中$C(P,x)$为满足$P_j\lt x(1\le j\le n)$的$j$的数目。
对于两个长度为$n$的排列$P_1,P_2$，定义函数$F(P_1,P_2)$等于满足$P_1[l\ldots r]$相似于$P_2[l\ldots r] (1\le l\le n)$并且$P_1[l\ldots r]$包含不超过$E$个逆序对的数对$(l,r)$的数目。
现在请你求出：对$P_1,P_2$分别取满$1\sim n$的排列后所有$F(P_1,P_2)$的和。
题目分析
题目的相似相当于离散化后都出现过。
考虑枚举相似子区间的长度。
对于长度为$i$的子区间，它有$n-i+1$个可出现位置。
设$f(i,j)$为长度为$i$的序列出现了$j$个逆序对的方案数。
这个DP以前做过，可以很简单的写出方程：
用前缀和优化一下转移。
每一个排列选出子区间后，其他位置可以任取，因此有$(n-i)!$种排列方法。
故长度为$i$对询问的贡献为：
代码
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
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=505,maxm=150005,maxq=10005;
const LL mod=1e9+7;
LL s[maxm],f[2][maxm],ans[maxq],C[maxn][maxn],fac[maxn],g[maxm];
struct Query {int n,e;} q[maxq];
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int main() {
int t=Get_Int();
for(int i=1; i<=t; i++)q[i].n=Get_Int(),q[i].e=Get_Int();
for(int i=0; i<=500; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
fac[0]=1;
for(int i=1; i<=500; i++)fac[i]=fac[i-1]*i%mod;
f[0][0]=1;
int now=0,pre=1;
for(int i=1; i<=500; i++) {
swap(now,pre);
for(int j=0; j<=i*(i-1)/2; j++) {
s[j]=(f[pre][j]+(j?s[j-1]:0))%mod;
f[now][j]=(s[j]-(j>=i?s[j-i]:0)+mod)%mod;
g[j]=(f[now][j]+(j?g[j-1]:0))%mod;
}
for(int j=1; j<=t; j++)if(q[j].n>=i) {
int n=q[j].n,e=min(q[j].e,i*(i-1)/2);
ans[j]=(ans[j]+g[e]*C[n][i]%mod*C[n][i]%mod*(n-i+1)%mod*fac[n-i]%mod*fac[n-i]%mod)%mod;
}
}
for(int i=1; i<=t; i++)printf("%lld\n",ans[i]);
return 0;
}
|
