原题目
求解思路：数学组合 + 容斥原理 先算出最多的 p 的序列的个数，为 n！，然后分别再算出由第一二个元素推出序列是 bad 的数量 res，在求出重叠算的数对的数量 m ，答案就是 n! - res + m
#include <bits/stdc++.h> using namespace std; #define ll long long const int mod = 998244353; const int maxn = 3e5+9; int n; pair<int ,int> a[maxn]; ll f[maxn]; int main(){ cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i].first >> a[i].second; } f[0]=1; //先计算出阶乘 for (int j = 1; j < maxn; ++j) { f[j]=(j*f[j-1])%mod; } ll ans = f[n]; for (int k = 0; k < 2; ++k) { sort(a,a+n); ll res=1; int i=0; while (i<n){ int j=i+1; //算出相同元素的个数 while(j<n&&a[j].first==a[i].first) ++j; //求阶乘 res = (res*f[j-i])%mod; i=j; } ans = (ans-res+mod)%mod; while(ans<0) ans+=mod; for (int l = 0; l < n; ++l) { swap(a[l].first,a[l].second); } } sort(a,a+n); ll res =1; int i=0; while(i<n){ int j=i+1; while(j<n&&a[j]==a[i]) ++j; res = (res%mod)*(f[j-i]%mod)%mod; i=j; } //如果第二个元素存在降序 for (int m = 1; m < n; ++m) { if(a[m].second<a[m-1].second) res=0; } ans = (ans%mod +res)%mod; cout << ans; return 0; }