Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing

一道容斥題

如果直接做就是找到所有出現過遞減的不同排列，當時硬鋼到自閉，然後在凱妹毀人不倦的教導下想到可以容斥做，就是：所有的排列設為a，只考慮第一個非遞減設為b，第二個非遞減設為c+兩個都非遞減的情況設為d，那麼正解就是a-b-c+d;

然後在text4上wa了無數次，為什麼全開long long還會出現負數結果呢，這時候一位美男子（沒錯又是凱妹）提示：因為我們的結果是mod998244353，如果a%998244353後是0，那麼a-b-c+d就會出現負數，而答案必為正，故wa。

註意到結果必為正，而且因為(b+c-d)為b,c在a範圍內的補集，不可能大於a，所以我們如果每一步都不mod（當然這會溢出），那麼最後結果必然是正數，所以我們在這裡加個判斷

if(ans>=0)
cout<<ans;
else
cout<<998244353+ans;//顯然0-b-c+d不可能>0，

最後AC了，感謝凱妹大佬，以下是代碼

題目鏈接https://codeforces.com/contest/1207/problem/D

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=1e9+7;
const int maxn=3e5+90;
const int mod=998244353;
long long n,m,x[maxn],y[maxn],mp[maxn];
ll jiecheng[maxn];
ll ans;
pair<int,int>p[maxn];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.second!=b.second){
return a.second<b.second;
}
else{
return a.first<b.first;
}
}
int main()
{
cin>>n;
mp[0]=x[0]=y[0]=jiecheng[0]=1;
p[0].first=-1;p[0].second=-1;
for(int i=1;i<=n;i++){
scanf("%d%d",&p[i].first,&p[i].second);
jiecheng[i]=jiecheng[i-1]*i%mod;
}
ans=jiecheng[n];
// cout<<ans<<endl;
sort(p+1,p+n+1);
// for(int i=1;i<=n;i++)
// cout<<p[i].first<<' '<<p[i].second<<endl;
// cout<<endl;
ll j=0;
for(int i=1;i<=n;i++){
if(p[i-1].first==p[i].first){
x[j]++;
}
else{
x[++j]=1;
}
}
long long t=1;
for(int i=1;i<=j;i++){
t=jiecheng[x[i]]*t%mod;
}
ans=ans-t%mod;t=1;
// cout<<ans<<endl;
sort(p+1,p+n+1,cmp);
// for(int i=1;i<=n;i++)
// cout<<p[i].first<<' '<<p[i].second<<endl;
// cout<<endl;
j=0;
for(int i=1;i<=n;i++){
if(p[i-1].second==p[i].second)
y[j]++;
else
y[++j]=1;
}
for(int i=1;i<=j;i++){
t=jiecheng[y[i]]*t%mod;
}
ans=(ans-t)%mod;
// cout<<ans<<endl;
j=0;
bool flag=0;
for(int i=1;i<=n;i++){
if(p[i]==p[i-1]){
mp[j]++;
flag=1;
}
else if(p[i-1].first<=p[i].first){
mp[++j]=1;
flag=1;
}
else{
flag=0;
break;
}
}
t=0;
if(flag){
t=1;
for(int i=0;i<=j;i++){
t=jiecheng[mp[i]]*t%mod;
}
}
ans=((long long)ans+t)%mod;
if(ans>=0)
cout<<ans;
else
cout<<mod+ans;
}