ccbeginner

TNFSHOJ 564

Oct 21st, 2020
620
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) (int)(X).size()
  5.  
  6. void extgcd(int a, int b, int &x, int &y){
  7.     if(b == 0){
  8.         x = 1;
  9.         y = 0;
  10.     }else{
  11.         extgcd(b, a%b, y, x);
  12.         y -= (a/b) * x;
  13.     }
  14. }
  15.  
  16. int moni(int k, int mod){
  17.     int x,y;
  18.     extgcd(k, mod, x, y);
  19.     return (x%mod+mod) % mod;
  20. }
  21.  
  22. const int M = 1e9+7;
  23. int form[1000001];
  24. int arr[1000001];
  25. int cnt[1000001];
  26. int n;
  27.  
  28. struct XD{
  29.     int idx,val,cur;
  30. }aux[1000001];
  31. bool cmp1(XD a, XD b){return a.val < b.val;}
  32. bool cmp2(XD a, XD b){return a.idx < b.idx;}
  33.  
  34. void discretize(){
  35.     for(int i = 0; i < n; ++i){
  36.         aux[i] = {.idx = i, .val = arr[i], .cur = 1};
  37.     }
  38.     sort(aux, aux+n, cmp1);
  39.     for(int i = 1; i < n; ++i){
  40.         if(aux[i].val == aux[i-1].val){
  41.             aux[i].cur = aux[i-1].cur;
  42.         }else{
  43.             aux[i].cur = aux[i-1].cur + 1;
  44.         }
  45.     }
  46.     sort(aux, aux+n, cmp2);
  47.     for(int i = 0; i < n; ++i){
  48.         arr[i] = aux[i].cur;
  49.     }
  50. }
  51.  
  52. int32_t main(){
  53.     cin >> n;
  54.     for(int i = 0; i < n; ++i)cin >> arr[i];
  55.     discretize();
  56.     form[0] = 1;
  57.     for(int i = 1; i <= n; ++i)form[i] = form[i-1] * i % M;
  58.     int bnd = 1;
  59.     for(int i = 0; i < n; ++i){
  60.         bnd = max(bnd, arr[i]);
  61.         ++cnt[arr[i]];
  62.     }
  63.     bool yes = 1;
  64.     int odd = 0;
  65.     int ans = 1;
  66.     if(n & 1){
  67.         for(int i = 1; i <= bnd && yes; ++i){
  68.             if((cnt[i] & 1) && odd != 0)yes = 0;
  69.             else if(cnt[i] & 1)odd = i;
  70.         }
  71.     }else{
  72.         for(int i = 1; i <= bnd && yes; ++i){
  73.             if(cnt[i] & 1)yes = 0;
  74.         }
  75.     }
  76.     //cout << yes << '\n';
  77.     if(yes){
  78.         for(int i = 1; i <= bnd; ++i){
  79.             ans = ans * form[cnt[i]] % M;
  80.             ans = ans * moni(form[cnt[i]/2], M) % M;
  81.         }
  82.         ans = ans * (form[n/2]) % M;
  83.         cout << ans << '\n';
  84.     }else{
  85.         cout << 0 << '\n';
  86.     }
  87.     return 0;
  88. }
RAW Paste Data