text: ## Educational Codeforces Round 71 (Rated for Div. 2) D - Number Of Permutations 转
  
  o
  osc_ogi0qclx
  
  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.
  
  [2,2] [3,1] [1,1]   [3,1] [2,2] [1,1] 符合条件。
  
  `````` 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
  
  ### osc_ogi0qclx
  
  CDH5: 使用parcels配置lzo
  
  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
  
  2012/11/04
  732
  0
  
  SQL 语句大全
  
  GeneralMa
  
  0
  0
  
  osc_qv1fwke0
  19分钟前
  7
  0
  
  zhang_rick
  
  0
  0
  
  osc_anefoz50
  19分钟前
  0
  0
  
  19分钟前
  13
  0