#6077. 「2017 山东一轮集训 Day7」逆序对
题目描述
给定 n,k n, kn,k，请求出长度为 n nn 的逆序对数恰好为 k kk 的排列的个数。答案对 109+7 10 ^ 9 + 7109+7 取模。
对于一个长度为 n nn 的排列 p pp，其逆序对数即满足 i<j i < ji<j 且 pi>pj p_i > p_jpi>pj 的二元组 (i,j) (i, j)(i,j) 的数量。
输入格式
一行两个整数 n,k n, kn,k。
输出格式
一行，表示答案。
样例
样例输入
7 12样例输出
531数据范围与提示
对于 20% 20\%20% 的数据，n,k≤20 n, k \leq 20n,k≤20；
对于 40% 40\%40% 的数据，n,k≤100 n, k \leq 100n,k≤100；
对于 60% 60\%60% 的数据，n,k≤5000 n, k \leq 5000n,k≤5000；
对于 100% 100\%100% 的数据，1≤n,k≤100000,1≤k≤(n2) 1 \leq n, k \leq 100000, 1 \leq k \leq \binom{n}{2}1≤n,k≤100000,1≤k≤(2n)。
#include<iostream>
#include<cstdio>
#include<cstring>
#define mod 1000000007
#define maxn 5002
using namespace std;
int dp[maxn][maxn],n,sum[maxn][maxn],m;
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int main(){
scanf("%d%d",&n,&m);m++;
dp[][]=;
sum[][]=;
int lim,i,j,l,r;
for(i=;i<=n;++i){
lim=(i-)*i/+;
for(j=;j<=min(lim,m);++j){
l=Max(j-i,);r=Min(j,(i-)*(i-)/+);
dp[i][j]=sum[i-][r]-sum[i-][l];
if(dp[i][j]<)dp[i][j]+=mod;
else if(dp[i][j]>=mod)dp[i][j]-=mod;
sum[i][j]=sum[i][j-]+dp[i][j];
if(sum[i][j]>=mod)sum[i][j]-=mod;
}
}
printf("%d",dp[n][m]);
return ;
}
60分 dp+前缀和优化
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 200010
#define mod 1000000007
using namespace std;
int n,k,S;
long long f[][maxn],inv[maxn],fac[maxn],a[maxn];
long long C(int n,int m){
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
long long Pow(long long x,int y){
long long res=;
while(y){
if(y&)res=res*x%mod;
x=x*x%mod;
y>>=;
}
return res;
}
int main(){
scanf("%d%d",&n,&k);
S=sqrt(k<<)+;
f[][]=;
for(int i=;i<=S;i++)
for(int j=i;j<=k;j++){
f[i][j]=(f[i][j-i]+f[i-][j-i])%mod;
if(j>n)f[i][j]=(f[i][j]-f[i-][j-n-])%mod;
}
fac[]=inv[]=;
for(int i=;i<=k+n;i++){
fac[i]=1LL*fac[i-]*i%mod;
inv[i]=Pow(fac[i],mod-);
}
long long ans=C(n+k-,n-);
for(int i=;i<=S && i<=n;i++){
long long cur=;
for(int j=;j<=k;j++)
cur=(cur+f[i][j]*C(n+k-j-,n-))%mod;
if(i&)cur=-cur;
ans=(ans+cur)%mod;
}
ans=(ans+mod)%mod;
cout<<ans;
}
100分