luogu2513 [HAOI2009]逆序对数列

题目描述

对于一个数列{ai}，如果有i< j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？

输入输出格式

输入格式：

第一行为两个整数n，k。

输出格式：

写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。

输入输出样例

输入样例#1：

4 1

输出样例#1：

3

说明

样例说明：

下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

测试数据范围

30%的数据 n<=12

100%的数据 n<=1000，k<=1000

题解

这题的做法非常的多，我用的最暴力的方法：直接递推

$f[i][j]$表示￥i￥个有￥j￥个逆序对。

我们考虑每一次的状态，比如$i=4,k=3$

这样就相当于考虑

• $1$后面加$(2,3,4),k=3$的方案数
• $2$后面加$(1,3,4),k=2$的方案数
• $3$后面加$(1,2,4),k=1$的方案数
• $4$后面加$(1,2,3),k=0$的方案数

看出一点规律了吧。

#include <cstdio>
#define N 1010
#define mod 10000
using namespace std;
int n,k,f[N][N];
main()
{
    scanf("%d%d",&n,&k);
    f[1][0]=1;
    f[2][0]=1;f[2][1]=1;
    f[3][1]=2;f[3][2]=2;f[3][3]=1;f[3][0]=1;
    for (int i=4;i<=n;i++)
    {
        f[i][1]=i-1,f[i][0]=1;
        for (int j=2;j<=k;j++)
            for (int l=1;l<=i&&l<=j+1;l++)
                f[i][j]+=f[i-1][j-l+1],f[i][j]%=mod;
    }
    printf("%d",f[n][k]%mod);
}