错题好题集第二篇。
题意
你需要构造一个长度为 \(n\) 的排列，使得它的逆序值恰好为 \(k\)。
逆序值的定义
对于一个排列 $p$，我们将其逆序值定义为至少包含一个逆序对的子段的数量。形式上，这就是满足以下条件的一对下标 $(i,j)$ 的整数 $(l,r)(1\le l < r\le n)$ 的个数：$l\le i < j\le r$ 且 $p_i>p_j$。\(n\le30,0\le k\le\frac{n(n-1)}{2}\)。
解法
Hint 1
注意 $n$ 的数据范围，是否有什么启发？Hint 2
考虑 $O(n^4)$ 的 dp。令 $dp_{i,j}$ 表示构造出长度为 $i$ 并且逆序值为 $j$ 的排列是否可行。如何求出这个 $dp$ 数组？Hint 3
如何通过这个 $dp$ 数组得到我们想要的排列？Solution
容易发现，假如我们在现在构造出的长为 $i$ 并且逆序值为 $j$ 的排列后面再加上长度为 $s$ 的递增序列，那么逆序值就会增加 $i\times s$。所以对于 $dp_{i,j}$，我们枚举要往后加上的长度 $s$，那它的下一个状态就是 $dp_{i+s,j+i\times s}$。所以如果 $dp_{i,j}$ 合法，那么 $dp_{i+s,j+i\times s}$ 也合法。所以我们再记录一个 $per_{i,j}$ 表示构造排列时最后加入的那一段的长度，用它来反推这个排列。于是我们就做完了。事实上，那个 \(O(n^4)\) 其实就是 \(30\times30\times900\)，能过。
Code
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define eb emplace_back
#define pb push_back
#define print(x,c) write(x),putchar(c),flush()
using namespace std;
typedef long long ll;
constexpr int N = 35;namespace FAST_IO {
#define IOSIZE 300000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template <typename T> inline void read (T &x) {x = 0; T f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();} x *= f;}
template <> inline void read (double &x) {x = 0; int f = 1;char ch = getchar();while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();} while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();if (ch == '.') {ch = getchar(); for (double t = 0.1; isdigit(ch); t *= 0.1) x += t * (ch - '0'), ch = getchar();}x *= f;}
inline bool read(char *s) {char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true;}
template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}
template <typename T> inline void write (T x) {if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48);}
inline void write(char *x) {while (*x) putchar(*x++);}
inline void write(const char *x) {while (*x) putchar(*x++);}
inline void flush() {if (p3 != obuf) {fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}
}
using namespace FAST_IO;int n, k;
bitset <N * N> dp[N];
int per[N][N * N];void work (int len, int k) {if (!len) return ;int l = per[len][k];for (int i = len - l + 1; i <= len; ++ i) print (i, ' ');work (len - l, k - l * (len - l));
}void solve() {read (n, k);if (dp[n][k]) work (n, k), putchar ('\n'), flush ();else print (0, '\n');
}int main() {dp[0][0] = 1;for (int i = 0; i <= 30; ++ i) {for (int j = 1; i + j <= 30; ++ j) {for (int k = 0; k + i * j <= 30 * 30; ++ k) {if (!dp[i][k] || dp[i + j][k + i * j]) continue;dp[i + j][k + i * j] = 1;per[i + j][k + i * j] = j;}}}int T;read (T);while (T --) solve ();return 0;
}