题解 SP64 【PERMUT1 - Permutations】
rui_er
2020-08-25 18:11:59
本题是三倍经验 [Link1](/problem/P2513) [Link2](/problem/P1521)，不知道为啥这几题难度评分不一样，区别只有多组数据和模数。
好了，下面进入正题。
---
题意简述：多组数据，给定 $n$，求 $1\sim n$ 的所有排列中逆序对个数恰有 $k$ 个的情况。
由于有多组数据，因此考虑预处理出所有情况后进行 $O(1)$ 查询，~~虽然这题数据范围较小好像也不用。~~
怎么进行预处理呢？考虑进行动态规划。
设计状态 $dp_{i,j}$ 表示对于 $1\sim i$ 的所有排列，恰有 $j$ 个逆序对的情况总数。
考虑如何进行转移。我们在 $1\sim i-1$ 的一个排列，添加一个数 $i$，此时我们可以使逆序对个数增加 $1,2,\cdots,i-1$ 个。因此，我们可以得到转移方程：
$$dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}$$
此时，根据我们状态的定义，$dp_{n,k}$ 即为所求。
---
这是我们注意到一个问题：这个转移是 $O(n^3)$ 的，无法通过上面两道双倍经验，因此需要优化。
看到我们最后一维要加的是一个区间内的 $dp$ 值，容易想到通过维护前缀和来优化时间。我们采取循环中滚动求前缀和的方式。
代码中的前缀和开的是数组，也有只用一个变量的做法（其实并不难），~~因为我懒~~，这里就不写了。
另外，由于数量可能很大，需要开 long long。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;
ll T, n, m;
ll dp[N][N] = {{0}, {1}}, s[N];
void dpInit() {
for(ll i=2;i<=1000;i++) {
memset(s, 0, sizeof(s));
for(ll j=0;j<=1000;j++) {
s[j] = dp[i-1][j];
if(j) s[j] += s[j-1];
dp[i][j] = s[j];
ll _ = j - i + 1;
if(_ >= 0) s[j] -= dp[i-1][_];
}
}
}
int main() {
dpInit();
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld", &n, &m);
printf("%lld\n", dp[n][m]);
}
return 0;
}
```