P2513 [HAOI2009]逆序对数列

题目描述

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

---

错误日志： 没想対， 菜是原罪， 最近状态不佳

---

Solution

在一段 \(1 - (i - 1)\) 的排列中加入 \(i\) 你可以控制 \(i\) 插入的位置， 给这个排列的逆序对任意加上 \(1 - (i - 1)\) 对（从最右到最左插入）

于是想到状态 \(dp[i][j]\) 表示为考虑 \(1 - i\) 的排列， 逆序对数为 \(j\) 的方案数

然后写出状态转移方程：$$dp[i][j] = \sum_{k = 0}^{min(j, i - 1)}dp[i - 1][j - k]$$

这样枚举 \(k\)， 复杂度为 \(O(nk^{2})\) 会炸

观察这个式子， 令 \(t = j - k\) ，换一下元， 交换 \(sum\) 的上下边界， 我们可以得到：$$dp[i][j] = \sum_{t = max(0, j - i +1)}^{j}dp[i - 1][t]$$

发现 \(t\) 的范围为一段可以维护和的区间， 前缀和维护即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

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

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

    return flag * out;

    }

const int maxn = 2019, M = 10000;

int num, K;

int dp[maxn][maxn];

int main(){

	num = RD(), K = RD();

	dp[1][0] = 1;

	REP(i, 2, num){

		int sum = 0;

		REP(j, 0, K){

			sum = (sum + dp[i - 1][j]) % M;

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

			dp[i][j] = sum;

			}

		}

	printf("%d\n", dp[num][K]);

	return 0;

	}