51nod 1020 逆序排列

Type:DP,逆序数

题目

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中,2 1,4 3,4 1,3 1是逆序,逆序数是4。

1-n的全排列中,逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)
给出2个数n和k,求1-n的全排列中,逆序数为k的排列有多少种?
例如:n = 4 k = 3。

1 2 3 4的排列中逆序为3的共有6个,分别是:
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3

由于逆序排列的数量非常大,因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。

Input

第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)
第2 – T + 1行:每行2个数n,k。中间用空格分隔。(2 <= n <= 1000, 0 <= k <= 20000)

Output

共T行,对应逆序排列的数量 Mod (10^9 + 7)

Input示例

1
4 3

Output示例

6

题解

考虑 dp[i][j] 表示 元素个数为 i 个时 逆序数为 j 的全排列个数为 dp[i][j] 个.

设当前元素为 N ,则 N 可以放在原来 N-1 个元素的任意全排列的 N-i(i∈[0,N)) 上的位置.

当 N 放在位置 N-i 上时,该排列的逆序数会增长 i (因为N最大,所以后面i个为逆序,前面为顺序),所以当我们想要找长度为 N ,逆序数为 k 的个数时,只需要找长度为 N-1 ,逆序数为 k-i 的全排列的个数即可.

所以 dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))

复杂度为 O(k(N^2)) 会炸.

考虑优化:

① dp[N][k] = lambda(dp[N-1][k-i] | i∈[0,N))
② dp[N][k-1] = lambda(dp[N-1][k-1-i] | i∈[0,N))
①-②: dp[N][k]-dp[N][k-1] = dp[N-1][k]-dp[N-1][k-N]
dp[N][k]=dp[N-1][k]-dp[N-1][k-N]+dp[N][k-1]

得出递推公式:

① dp[i][j]=1 j=0
② dp[i][j]=dp[i-1][j]-dp[i-1][j-i]+dp[i][j-1]

由题目的约束条件:

逆序数最小为0(正序),最大为n*(n-1) / 2(倒序)

故枚举逆序数只需要枚举到 i*(i-1)/2&&j\<20000即可
注意j-i不能<0

Code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1010][20010];

void init(){
    for(int i=1;i<=1000;++i) dp[i][0]=1;
    for(int i=2;i<=1000;++i){
        for(int j=1;j<=i*(i-1)/2&&j<=20000;++j){
            dp[i][j]=(dp[i][j-1]+dp[i-1][j])%mod;
            if(j-i>=0)dp[i][j]=(((dp[i][j]-dp[i-1][j-i])%mod)+mod)%mod;
        }
    }
}

int main(){
    init();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        printf("%d\n",dp[n][k]);
    }
    return 0;
}

2018年全国多校算法寒假训练营练习比赛(第五场) A 逆序数

链接:https://www.nowcoder.com/acm/contest/77/A
来源:牛客网

题目描述

在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2, 那么这个序列的逆序数为7,逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述:

第一行有一个整数n(1 <= n <= 100000), 然后第二行跟着n个整数,对于第i个数a[i],(0 <= a[i] <= 100000)。

输出描述:

输出这个序列中的逆序数

示例1

输入

5
4 5 1 3 2

输出

7

两种方法求逆序数

归并排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100010;

int seq[maxn],N;
int temp[maxn];
LL cnt;
//归并排序求逆序数
void merge_sort(int arr[],int l,int r){
    if(l==r)return;
    int mid=((l+r)>>1);
    merge_sort(arr,l,mid);
    merge_sort(arr,mid+1,r);
    int i=l,j=mid+1;
    for(int k=l;k<=r;++k){
        if(j>r || (i<=mid && arr[i]<arr[j]))temp[k]=arr[i++];
        else temp[k]=arr[j++],cnt+=mid-i+1;
        //如果a[i]>a[j]则逆序数加上mid+1-i,即剩下的前面个数
    }
    for(i=l;i<=r;++i)arr[i]=temp[i];
}

int main(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>seq[i];
    }
    cnt=0;
    merge_sort(seq,0,N-1);
    cout<<cnt<<endl;
    return 0;
}

树状数组