感觉这个题还是挺不错的。
考虑 F1。考察 \(a_i\) 差分后的意义,发现 \(a_i - a_{i - 1}\) 就是 \((\sum\limits_{j = 1}^{i - 1} [p_j = i]) + p_i \le i\)。
考虑将其转化为棋盘问题。在 \((i, p_i)\) 放一个车,那么 \(a_i - a_{i - 1}\) 就是 \((1, i) \sim (i, i)\) 和 \((i, 1) \sim (i, i - 1)\) 这些格子组成的“L”字形的车的数量。
一个放车的方案合法当且仅当所有车互不攻击。因此容易发现合法的 \(a_i - a_{i - 1}\) 一定 \(\in [0, 2]\)。考虑从前往后扫,同时维护答案 \(ans\) 和现在还没被占用的行(列)数量 \(t\)。
- 若 \(a_i = a_{i - 1}\),无事发生,多了第 \(i\) 行和列没被占用,因此 \(t \gets t + 1\)。
- 若 \(a_i - a_{i - 1} = 1\),相当于可以在 \((1, i) \sim (i - 1, i)\) 和 \((i, 1) \sim (i, i - 1)\) 中还没被占用的格子放车,同时也可以在 \((i, i)\) 放车,那么 \(ans \gets ans \times (2t + 1)\),\(t\) 不变。
- 若 \(a_i - a_{i - 1} = 2\),\((1, i) \sim (i - 1, i)\) 和 \((i, 1) \sim (i, i - 1)\) 中还没被占用的格子各放一个车,那么 \(ans \gets ans \times t^2\),然后 \(t \gets t - 1\)。
如上讨论可以通过 F1。
F2 我们继续将其放到棋盘上考虑。考虑一个 \(a_i \ne -1\) 的位置 \(i\),设它上一个 \(a_j \ne -1\) 的位置是 \(j\)。现在相当于求在 \(x \times x\) 的左下角抠掉了 \(y \times y\) 的一块的“L”字形棋盘放 \(t\) 个互不攻击的车的方案数,其中 \(x = j - a_j, y = i - a_j, t = a_i - a_j\)。每个这样的“L”字形互相独立,所以可以直接把方案乘起来。
上面的问题可以考虑容斥(我现在还不会不容斥的做法?)。相当于在左下角 \(y \times y\) 的区域不能放车,那么我钦定 \(i\) 个车放在了左下角,设 \(F(n, m)\) 为 \(n \times n\) 的棋盘放 \(m\) 个互不攻击的车的方案数,那么这部分的方案为 \(F(x, i) \times F(y - i, t - i)\),容斥系数为 \((-1)^i\),因此结果为:
最后一个问题是求 \(F(n, m)\)。考虑先选 \(m\) 行放车,有 \(\frac{n!}{(n - m)!}\) 种选列的方案,那么 \(F(n, m) = \binom{n}{m} \times \frac{n!}{(n - m)!}\)。
容易发现 \(\sum t = n\),所以时间复杂度为 \(O(n)\)。
code
// Problem: F2. Small Permutation Problem (Hard Version)
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/F2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], a[maxn], ifac[maxn];
inline ll A(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[n - m] % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline ll F(ll n, ll m) {
return C(n, m) * A(n, m) % mod;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
a[0] = 0;
if (a[n] != -1 && a[n] != n) {
puts("0");
return;
}
a[n] = n;
int j = 0;
ll ans = 1;
for (int i = 1; i <= n; ++i) {
if (a[i] != -1) {
int t = a[i] - a[j], x = j - a[j], y = i - a[j];
if (t < 0) {
puts("0");
return;
}
ll res = 0;
for (int i = 0; i <= x && i <= t; ++i) {
res = (res + ((i & 1) ? mod - 1 : 1) * F(x, i) % mod * F(y - i, t - i)) % mod;
}
ans = ans * res % mod;
j = i;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Permutation CodeForces Problem Version 1909F2permutation problem version 1909f permutation codeforces problem 1909i permutation codeforces problem version codeforces factory version 1919f2 permutation codeforces another problem 1909f2 permutation another problem 1858c codeforces 1909d split plus codeforces pumping 1909g lemma 题解permutation another problem