ABC134_F Permutation Oddness
Ameiyo
·
·
个人记录
ABC134_F Permutation Oddness
题目连接
一道想到就不难的dp。
首先看数据范围， n \le 50 ，一个说大不大说小不小的让人难受的范围。。。
那么状压也肯定不行，考虑把每个数的贡献独立出来。
对于一个数 i 来说，他所放的位置有三种情况：
- 放在第 i 位前面
这个时候，他的贡献要么是 i + i （放在第 i 位的数小于 i ），或者是 i - i （放在第 i 位的数大于 i ）。
- 放在第 i 位
此时贡献只能为 0 。
- 放在第 i 位后面
这时，他的贡献就是 - i + i （放在第 i 位的数小于 i ），或者是 - i - i （放在第 i 位的数大于 i ） 。
所以说，与一个数 i 有关的贡献就是 第 i 位的那个下标，以及 i 这个数本身。
但是因为还要确定 i 能不能放到前面，或者第 i 位能不能放比 i 小的数，所以状态中还要多一维，表示有多少个位置是空的，其实也就是有多少个数没放。
那么转移有点多，见代码。
```cpp
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define reg register
#define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i)
#define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i)
template <typename _typer> inline _typer read() {
_typer init = 0;
char ch = getchar(), k = 0;
for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
for ( ; isdigit(ch); ch = getchar())
init = (init << 3) + (init << 1) + (ch ^ 48);
return k ? -init : init;
}
const ll N = 55, INF = 1e9;
const ll M = 5005, Mod = 1e9 + 7;
int n, m;
ll f[N][N][M];
int main() {
n = read<int>(), m = read<int>();
f[0][0][2500] = 1;
rep (i, 0, n - 1) {
rep (j, 0, i) rep (k, 0, 5000) {
// 1 选一个空位放并且选一个数放自己这
if (j > 0 && k + 2 * i <= 5000)
(f[i + 1][j - 1][k + 2 * i] += f[i][j][k] * j * j) %= Mod;
// 2 选一个空位放i，然后自己空出来
(f[i + 1][j][k] += f[i][j][k] * j) %= Mod;
// 3 放自己
(f[i + 1][j][k] += f[i][j][k]) %= Mod;
// 4 选一个放自己这，然后空位不变
(f[i + 1][j][k] += f[i][j][k] * j) %= Mod;
// 5 自己空出来
if (k - 2 * i >= 0)
(f[i + 1][j + 1][k - 2 * i] += f[i][j][k]) %= Mod;
}
}
// 每个数都放了
cout << f[n][0][2500 + m] << endl;
return 0;
}
```