设为首页 加入收藏

TOP

Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
2019-09-03 03:46:41 】 浏览:20
Tags:Educational Codeforces Round Rated for Div. 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;
}


Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing https://www.cppentry.com/bencandy.php?fid=102&id=249818

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇MSSQLSERVER 服务运行内存设置较.. 下一篇Win7原装ISO镜像封装USB3.0&网卡..