#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

样例输出

数据范围与提示

对于 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分

秒客网

loj #6077. 「2017 山东一轮集训 Day7」逆序对