AC475B 2024省选联测26 排列
题意
对于所有满足 \(1 \le a < b \le n\) 的 \((a, b)\) 的排列，需要满足：
- 对于 \(1\le a < b < c \le n\)，\((a, c)\) 处在 \((a, b)\) 和 \((b, c)\) 之间。
- 另外再给出 \(m\) 个限制，形如 \((a, b, c, d)\) 要求 \((a, b)\) 在 \((c, d)\) 的前面。
Sol
其实这道题没有那么 hard。
首先先抛开 \(m\) 个限制。
trivial 地，考虑对于 \((a, b)\) 排列的每个区间，都满足包含 \((a, b)\) 和 \((b, c)\) 也包含 \((a, c)\)。
一眼传递闭包。
考虑将每个点对 \((a, b)\) 抽象为一条 \(a \to b\) 的边。
那么原来的排列，就被抽象为了一张完全图的加边过程。
这个过程满足什么呢？
满足对于当前时刻的任意位置，图和补图都有传递性。
我们发现这样的图只有 \(n!\) 个，到这里就已经做完了。
为什么呢？
我们把 \(n!\) 个排列拿出来，考虑对于逆序对连边，这样就恰好对应一个具有联通性的 DAG 了。
剩下简单计数，然后再判下 \(m\) 个条件即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
#include <vector>
#define int long long
#define tupl tuple <int, int, int, int>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 15, M = 4e6 + 5, mod = 998244353;
vector <tupl> qrl;
array <int, N> fac, idx, cur, isl;
array <int, M> f;
void Mod(int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
signed main() {
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
tupl x;
get <0>(x) = read(), get <1>(x) = read();
get <2>(x) = read(), get <3>(x) = read();
qrl.push_back(x);
}
fac[0] = 1;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod, idx[i] = i;
int T = 0;
f[1] = 1;
do {
cur.fill(0); T++;
for (int i = 1; i <= n; i++) {
isl[idx[i]] = i;
for (int j = i + 1; j <= n; j++)
if (idx[j] < idx[i])
cur[i]++;
}
bool flg = 0;
for (auto k : qrl)
if (isl[get <0>(k)] > isl[get <1>(k)] &&
isl[get <2>(k)] < isl[get <3>(k)])
flg = 1;
if (flg) continue;
for (int i = 1; i < n; i++) {
if (idx[i] > idx[i + 1]) continue;
int tp0 = T - cur[i] * fac[n - i]
- cur[i + 1] * fac[n - i - 1]
+ (cur[i + 1] + 1) * fac[n - i]
+ cur[i] * fac[n - i - 1];
f[tp0] += f[T], Mod(f[tp0]);
}
} while (next_permutation(idx.begin() + 1, idx.begin() + 1 + n));
write(f[fac[n]]), puts("");
return 0;
}