P2513 [HAOI2009] 逆序对数列
题目描述
对于一个数列 ，如果有 且 ，那么我们称 与 为一对逆序对数。
若对于任意一个由 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 的这样自然数数列到底有多少个？
输入格式
第一行为两个整数 。
输出格式
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对 求余数后的结果。
解析
考虑向 组成的数列中插入一个 ，由于 比数列中所有元素都大，所以新的数列可以比原来多出 个逆序对。
用 表示 的数列有 个逆序对的方法数，初始状态 ，状态转移方程为：
用前缀和数组解决求和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e3 + 5, MOD = 10000;
int dp[N][N], sum[N][N];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
dp[i][0] = sum[i][0] = 1;
int j;
for (j = 1; j <= k; ++j) {
dp[i][j] = sum[i-1][j] - (j-i>=0 ? sum[i-1][j-i] : 0);
sum[i][j] = sum[i][j-1] + dp[i][j];
sum[i][j] %= MOD;
dp[i][j] %= MOD;
if (sum[i][j] < 0) sum[i][j] += MOD;
if (dp[i][j] < 0) dp[i][j] += MOD;
}
sum[i][j] = sum[i][j-1];
}
cout << dp[n][k];
}
|