[HAOI2009]逆序对数列

题意

洛谷 P2513 [HAOI2009]逆序对数列

求\(1...n\)的所有排列中有多少个排列含有\(k\)个逆序对.答案对\(10^4\)取模.

\(1\le n,k\le1000\).

思路1 暴力

暴力枚举全排列,树状数组求逆序对.

时间复杂度\(O(n!\times n\log n)\).

#include<bits/stdc++.h>
const int SIZE=15;
int n,m,C[SIZE],T[SIZE],Ans;
bool mk[SIZE];

void Change(int i,int x)
{
    for(;i<=n;i+=i&(-i))
        T[i]+=x;
}
int sum(int i)
{
    int x=0;
    for(;i;i-=i&(-i))
    {
        x+=T[i];
    }
    return x;
}
int Do()
{
    memset(T,0,sizeof(T));
    int x=0;
    for(int i=1;i<=n;i++)
    {
        x+=sum(n)-sum(C[i]);
        Change(C[i],1);
    }
    return x;
}

void DFS(int step)
{
    if(step==n+1)
    {
        if(Do()==m)++Ans;
        return;     
    }
    for(int i=1;i<=n;i++)
    {
        if(!mk[i])
        {
            mk[i]=1;
            C[step]=i;
            DFS(step+1);
            mk[i]=0;
        }
    }
}


int main()
{
    scanf("%d%d",&n,&m);
    DFS(1);
    printf("%d",Ans);
    return 0;
}

思路2 动态规划

设\(DP[i,j]\)表示\(1...i\)的所有排列中,逆序对数为\(j\)的排列个数.

考虑如何由\(DP[i,...]\)向\(DP[i+1,...]\)转移.

容易发现,这个转移的含义是,把数字\(i+1\)插入到一个\(1...i\)的排列中的某个位置,所带来的逆序对数的改变.

由于\(i+1\)比\(1...i\)中任何一个数都要大,那么\(i+1\)与插入的位置以后的所有数,一定形成新的逆序对,与插入的位置以前的所有数,一定不形成新的逆序对.

换句话说,如果我们把\(i+1\)插入到该排列的第\(k\)个数后面,那么新形成\(i-\)个k逆序对.

考虑枚举\(k\),那么有:

\[DP[i,j]=\sum_{k=j-(i-1)}^{j}DP[i-1,k]\]

于是可以枚举\(i,j,k\),求出所有\(DP[]\)的值,总时间复杂度\(O(nk^2)\).

#include<bits/stdc++.h>
const int SIZE=1005,Mod=10000;

int n,m,DP[SIZE][SIZE];
int main()
{
    scanf("%d%d",&n,&m);
    DP[1][0]=1;
    for(int i=2;i<=n;i++)
        for(int k=0;k<=m;k++)
            for(int p=std::max(k-(i-1),0);p<=k;p++)
            {
                DP[i][k]+=DP[i-1][p];
                DP[i][k]%=Mod;
            }
    printf("%d",DP[n][m]);
    return 0;
}

思路3 动态规划

发现思路 2 中最内层循环是一段区间和,可以用前缀和快速求出.时间复杂度降至\(O(nk)\).

#include<bits/stdc++.h>
const int SIZE=1005,Mod=10000;
using namespace std;

int n,m,DP[SIZE][SIZE],sum[SIZE];
int main()
{
    scanf("%d%d",&n,&m);
    DP[1][0]=1;
    for(int k=0;k<=m;k++)
        sum[k]=1;
    for(int i=2;i<=n;i++)
    {
        for(int k=0;k<=m;k++)
        {
            int p=max(k-(i-1),0)-1,Tem;
            if(p>=0)Tem=sum[p];
            else Tem=0;
            DP[i][k]=(sum[k]-Tem+Mod)%Mod;
        }
        sum[0]=DP[i][0];
        for(int k=1;k<=m;k++)
            sum[k]=(sum[k-1]+DP[i][k])%Mod; 
    }
    printf("%d",DP[n][m]);
    return 0;
}

[HAOI2009]逆序对数列

原文：https://www.cnblogs.com/TaylorSwift13/p/11774935.html