文档章节

Educational Codeforces Round 71 (Rated for Div. 2) D - Number Of Permutations

o
 osc_ogi0qclx
发布于 2019/08/24 19:33
字数 1082
阅读 13
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

原文链接:https://www.cnblogs.com/xwl3109377858/p/11405773.html

Educational Codeforces Round 71 (Rated for Div. 2)

D - Number Of Permutations

You are given a sequence of n pairs of integers: (a1,b1),(a2,b2),…,(an,bn). This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:

  • s=[(1,2),(3,2),(3,1)] is bad because the sequence of first elements is sorted: [1,3,3];
  • s=[(1,2),(3,2),(1,2)] is bad because the sequence of second elements is sorted: [2,2,2];
  • s=[(1,1),(2,2),(3,3)] is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;
  • s=[(1,3),(3,3),(2,2)] is good because neither the sequence of first elements ([1,3,2]) nor the sequence of second elements ([3,3,2]) is sorted.

Calculate the number of permutations of size n such that after applying this permutation to the sequence s it turns into a good sequence.

A permutation p of size n is a sequence p1,p2,…,pn consisting of n distinct integers from 1 to n (1≤pi≤n). If you apply permutation p1,p2,…,pn to the sequence s1,s2,…,sn you get the sequence sp1,sp2,…,spn. For example, if s=[(1,2),(1,3),(2,3)] and p=[2,3,1] then s turns into [(1,3),(2,3),(1,2)].

Input

The first line contains one integer n (1≤n≤3⋅105).

The next n lines contains description of sequence s. The i-th line contains two integers ai and bi (1≤ai,bi≤n) — the first and second elements of i-th pair in the sequence.

The sequence s may contain equal elements.

Output

Print the number of permutations of size n such that after applying this permutation to the sequence s it turns into a good sequence. Print the answer modulo 998244353 (a prime number).

Examples

input

3

1 1

2 2

3 1

output

3

input

4

2 3

2 2

2 1

2 4

output

0

input

3

1 1

1 1

2 3

output

4

Note

In first test case there are six permutations of size 3:

  1. if p=[1,2,3], then s=[(1,1),(2,2),(3,1)] — bad sequence (sorted by first elements);
  2. if p=[1,3,2], then s=[(1,1),(3,1),(2,2)] — bad sequence (sorted by second elements);
  3. if p=[2,1,3], then s=[(2,2),(1,1),(3,1)] — good sequence;
  4. if p=[2,3,1], then s=[(2,2),(3,1),(1,1)] — good sequence;
  5. if p=[3,1,2], then s=[(3,1),(1,1),(2,2)] — bad sequence (sorted by second elements);
  6. if p=[3,2,1], then s=[(3,1),(2,2),(1,1)] — good sequence.

 

题意:题目要求使二元组序列中x和y都不递增的排列的数量,

例如二元组 [1,1] [2,2] [3,1] 有三种 [2,2] [1,1] [3,1] 

  [2,2] [3,1] [1,1]   [3,1] [2,2] [1,1] 符合条件。

思路:考虑到求不递增的排列比较难,我们可以反过来考虑求递增的排列,

然后用全排列的数量即阶乘减去递增序列数量即为答案。

求递增的排列时要考虑单个x和y排列中重复元素数量,

而x与y同时递增时有重复的二元组我们应该减掉。

例如 [1,2] [3,4] [3,4] [5,6],计算单个排列x和y里计算后排列数量都为2,

但是二元组重复了排列数量2,所以答案为n阶乘减去2而不是减4。

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<stack>
11 #include<list>
12 //#include<unordered_map>
13 using namespace std;
14 #define ll long long
15 const int inf=1e9+7;
16  
17 const int maxn=3e5+10;
18 const int mod=998244353;
19 ll int jiecheng[maxn];//记录阶乘 
20 
21 pair<int,int> p[maxn];//pair数组 
22 
23 map<pair<int,int>,int>mp1;//记录重复二元组数 
24 
25 map<int,int>x;//标记 
26 map<int,int>y;
27 
28 bool cmp(const pair<int,int> &a,const pair<int,int> &b)
29 {                        //令x递增顺序排 
30     if(a.first != b.first)
31         return a.first < b.first;
32     else
33         return a.second < b.second;
34 }
35 
36 int main()
37 {
38     ios::sync_with_stdio(false);
39     
40     int n;
41     cin>>n;
42     
43     x.clear();//初始化 
44     y.clear();
45     mp1.clear();
46     
47     jiecheng[0]=1;
48     for(int i=1;i<=n;i++)
49     {
50         cin>>p[i].first>>p[i].second;
51         jiecheng[i]=jiecheng[i-1]*i%mod;//算阶乘 
52         x[p[i].first]++;//标记 
53         y[p[i].second]++;
54         mp1[p[i]]++;//标记二元组 
55     }
56     
57     sort(p+1,p+n+1,cmp);//排序 
58     
59     ll int flag=1;
60     
61     for(int i=2;i<=n;i++)//看x,y是否同时递增 
62     {
63         if(!(p[i-1].first<=p[i].first&&p[i-1].second<=p[i].second))
64         {
65             flag=0;//不符合 
66             break;
67         }
68     }
69     ll int ans=0;
70     
71     if(flag==1)//x,y同时递增 
72     {
73         for(auto it=mp1.begin();it!=mp1.end();it++)
74             flag=flag*jiecheng[it->second]%mod;
75         ans=mod-flag;//减去重复情况 
76     }
77     
78     ll int res=1;
79     
80     for(auto it=x.begin();it!=x.end();it++)//累加x 
81         res=res*jiecheng[it->second]%mod;
82     ans=(ans+res)%mod;
83     
84     res=1;
85     for(auto it=y.begin();it!=y.end();it++)//累加y 
86         res=res*jiecheng[it->second]%mod;
87     ans=(ans+res)%mod;
88     
89     ans=(jiecheng[n]-ans+mod)%mod;//全排列减去所有递增为最终答案 
90     
91     cout<<ans<<endl;
92     
93     return 0;
94 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
CDH5: 使用parcels配置lzo

一、Parcel 部署步骤 1 下载: 首先需要下载 Parcel。下载完成后,Parcel 将驻留在 Cloudera Manager 主机的本地目录中。 2 分配: Parcel 下载后,将分配到群集中的所有主机上并解压缩。 3 激...

cloud-coder
2014/07/01
6.8K
1
JavaScript 模板引擎--fragment.js

Fragment.js 允许你加载 html 碎片到任何元素中,只需要使用 data-fragment 属性。 <div data-fragment="fragment.html"></div> 也可通过 JSON 进行加载,如: <div data-fragment-json="fra......

匿名
2013/03/24
2.4K
0
CSS 选择器--Q.js

1, 和Sizzle的兼容 Q(expr, context, result, seed) Q.matches 支持Sizzle特别的setFilter伪类如:even,:first,:last,:lt... 支持复杂的:not和:has选择器(和sizzle一样) 2, 结果的正确性 Si...

hackwaly
2012/10/23
4.6K
0
iOS 的 Canvas 和 Audio 实现--Ejecta

Ejecta 是一个快速开源的 JavaScript、Canvas 和 音频实现,适用于 iOS 平台。你可以把它想象成一个只支持显示 Canvas 元素的浏览器,它像一个浏览器却无需浏览器,适用于游戏和动画开发。无...

匿名
2012/10/26
4.4K
0
ZimbraBackend

开源Z-push(http://z-push.sourceforge.net)的Zimbra后端的ActiveSync实现。支持推送电子邮件、同步联系人、日历、任务等在Zimbra和具有ActiveSync功能的设备。 特性: ActiveSync Push Em...

匿名
2012/11/04
732
0

没有更多内容

加载失败,请刷新页面

加载更多

SQL 语句大全

点击上方“掌上编程”,选择“置顶或者星标” 优质文章第一时间送达! 一、基础 「1、说明:创建数据库」 CREATE DATABASE database-name    「2、说明:删除数据库」 drop database ...

GeneralMa
昨天
0
0
山东创睦网络科技有限公司:使用Python爬取全球新冠肺炎疫情数据

使用Python爬取全球新冠肺炎疫情数据 导入所需库包 获取实时数据的url 正式编写程序 查看输出结果 导入所需库包 在获取数据之前,我们需要先安装好所需的包requests和pandas: 1.如果是使用p...

osc_qv1fwke0
19分钟前
7
0
如何1年获得别人3年的工作经验(深度好文)

最近有同学问我,为什么你的工作年限不长,技术却这么厉害,我笑了笑,啥也没说。 我不是不想回答,是不知道怎么回答。在他们的定位可能就是,每方面都懂一点,遇到问题能够快速解决,就是比...

zhang_rick
今天
0
0
新基建带动行业

什么是“新基建”? 什么是“新基建”? 根据央视发布的信息来看,其涵盖了5G基站建设、新能源汽车充电桩、大数据中心、人工智能、工业互联网,特高压,城际以及城轨交通,涉及了七大领域和相...

osc_anefoz50
19分钟前
0
0
怕入错行?这群技术人写了本“择业指南”

计算机专业好找工作吗?哪些方向是当前的主流和热门方向呢? 计算机专业的你是不是还在为职业发展纠结犹豫呢? 刚经历完高考选专业的你是不是还在迷茫徘徊呢? 那么福利来啦! 《软件技术职业...

阿里云云栖号
19分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部