题解【洛谷P2513/CJOJ1345】[HAOI2009]逆序对数列

Description

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

Input

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

Output

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

Sample Input

4 1

Sample Output

3

Hint

样例说明：
下列3个数列逆序对数都为1；
分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

测试数据范围
30%的数据 n＜=12
100%的数据 n＜=1000，k＜=1000

Source

HAOI，分治，递推

Solution

考虑DP。

dp[i][j]表示i的排列中逆序对数为j的方案数。

考虑i的放置,i为最大值,所以放在i-1个位置都可以计算出对答案的贡献，因此DP递推式为：

dp[i][j]=Σdp[i-1][k] (j-i+1<=k<=j)

考虑特殊情况：到i时最多可以贡献i-1对逆序对，所以从dp[0]~dp[j-i+1]这一段不能加！

但是这个算法要枚举i、j和k，时间复杂度为n^3，绝对TLE，因此考虑前缀和优化。

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read()
{
    int f = 1, x = 0;
    char c = getchar();

    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }

    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }

    return f * x;
}

const int mod = 10000;

int n, m, dp[1005][1005];

signed main()
{
    n = read(), m = read();

    dp[1][0] = 1;

    for (register int i = 2; i <= n; i++)
    {
        int sum = 0;

        for (register int j = 0; j <= m; j++)
        {
            sum = (sum + dp[i - 1][j]) % mod;

            dp[i][j] = sum;

            if (j - i + 1 >= 0)
            {
                sum = (sum - dp[i - 1][j - i + 1] + mod) % mod;
            }
        }
    }

    printf("%lld", dp[n][m]);

    return 0;
}