题目传送门
题目翻译
给定一个 \(d\)，接下来 \(d\) 行，每行一个 \(n\) 和 \(k\) 查找这个序列的全排列中一共有多少个排列含有 \(k\) 个逆序对。
思路
动态规划。
设 \(f_{i,j}\) 表示 \(1\) 到 \(i\) 中存在 \(j\) 个逆序对，所以方程为:
\[f_{i,j}= \sum ^j _{k=j-\min(i-1,j)}
f_{i-1,k}= \sum ^j _{k=0} f_{i-1,k} - \sum ^{j-\min(i-1,j)} _{k=0} f_{i-1,k}
\]
Q: 可这复杂度也太高了吧。
A: 别怕，可以用前缀和来优化。
优化详见注释。
CODE
#include <bits/stdc++.h>
using namespace std;
long long f[10010], g[2][10010];
int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int d;cin >> d;while (d--) {int n, k;cin >> n >> k;memset(f, 0, sizeof(f)); // 清空数组。memset(g, 0, sizeof(g)); // 同上。f[0] = 1; // 边界。for (int i = 0; i <= k; i++)g[1][i] = ((i == 0) ? 0 : g[1][i - 1]) + f[i]; // 前缀和。for (int i = 2; i <= n; i++)for (int j = 0; j <= k; j++) // 方程。{f[j] = g[(i - 1) & 1][j] - ((j - min(i - 1, j) - 1 < 0) ? 0ll : g[(i - 1) & 1][j - min(i - 1, j) - 1]);g[i & 1][j] = ((j == 0) ? 0 : g[i & 1][j - 1]) + f[j];}cout << f[k] << "\n"; // 输出答案。}return 0; // 结束。
}
彩蛋
本题是多倍经验 P6323 [COCI2006-2007#4] ZBRKA，P1521 求逆序对，P2513 [HAOI2009] 逆序对数列。