Problem - D. Number Of Permutations

传送门

容斥原理

思路：利用容斥，首先所有可能的排列肯定是fac[n]，然后可能会有三种 bad 的情况：

①第一个元素的排列是非递减

②第二种是第二个元素的排列是非递减

③这两个可能出现的重叠情况，意思就是说同时导致①②成立

这个时候我们利用容斥的思想，用fac[n]-①-②+③即可

我们把所有的pair按照第一个元素优先排列的方式把所有的pair sort 一下（ sort 对pair的排序方式是默认第一个元素优先的），这个时候我们就保证了所有pair的第一个元素组成的排列的肯定是一个不严格递增的排列

求③的时候需要注意的一点是，在已经按照第一个元素排完序之后，如果存在s[i+1].se<s[i].se，那么就表示不会有第三种情况发生因为s[i].fi<=s[i+1].fi所以如果按照第二个元素非降序排序的话，就会导致s[i+1].fi<s[i].fi，所以，如果出现这种情况则表明③=0

code

#include <bits/stdc++.h>

using namespace std;
#define int long long
typedef pair<int, int> pii;
const int mod = 998244353, N = 3e5 + 5;
pii s[N];
int fac[N];
map<pii, int> ab;
map<int, int> a, b;

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr), cout.tie (nullptr);
    int n;
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i)
        fac[i] = fac[i - 1] * i % mod;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        a[x]++, b[y]++, ab[{x, y}]++;
        s[i] = make_pair (x, y);
    }
    sort (s + 1, s + n + 1);
    int ans = fac[n], temp = 1;
    for (auto i: a)
        temp = temp * fac[i.second] % mod;
    ans = (ans - temp + mod) % mod, temp = 1;
    for (auto i: b)
        temp = temp * fac[i.second] % mod;
    ans = (ans - temp + mod) % mod, temp = 1;
    for (auto i: ab)
        temp = temp * fac[i.second] % mod;
    for (int i = 1; i < n; ++i)
        if (s[i + 1].second < s[i].second) temp = 0;
    ans = (ans + temp) % mod;
    cout << ans << endl;
    return 0;
}