Guest User

Untitled

a guest
May 24th, 2016
186
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <list>
  2. #include <map>
  3. #include <set>
  4. #include <deque>
  5. #include <stack>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <memory.h>
  15. #include <ctime>
  16. #include <bitset>
  17.  
  18. using namespace std;
  19.  
  20. #define ABS(a) ((a>0)?a:-(a))
  21. #define MIN(a,b) ((a<b)?(a):(b))
  22. #define MAX(a,b) ((a<b)?(b):(a))
  23. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  24. #define MEMS(a,b) memset((a),(b),sizeof(a))
  25. #define FI(i,n) for (int i=0; i<(n); ++i)
  26. #define pnt pair <int, int>
  27. #define mp make_pair
  28. #define LL long long
  29. #define U unsigned
  30.  
  31. LL tot[8000010];
  32. int sq[1000010];
  33. int a[4010];
  34. int cnt[1000010];
  35. vector<int> b;
  36.  
  37.  
  38. int main()
  39. {
  40. #ifdef Fcdkbear
  41.         freopen("in.txt", "r", stdin);
  42.         //freopen("out.txt", "w", stdout);
  43.         double beg = clock();
  44. #endif
  45.  
  46.         int n;
  47.         scanf("%d",&n);
  48.         FOR(i,0,n) {
  49.             scanf("%d",&a[i]);
  50.             b.push_back(a[i]);
  51.             cnt[a[i]]++;
  52.         }
  53.         sort(b.begin(),b.end());
  54.         b.resize(unique(b.begin(),b.end()) - b.begin());
  55.         int idx = 0;
  56.         FOR(i,0,n) {
  57.             FOR(j,i+1,n) {
  58.                 LL v = a[i]*1ll*a[j];
  59.                 tot[idx++] = v;
  60.                 if (a[i] == a[j])
  61.                     sq[a[i]]++;
  62.             }
  63.         }
  64.         sort(tot,tot+idx);
  65.         LL res = 0;
  66.         int c = 1;
  67.         FOR(i,1,idx) {
  68.             if (tot[i] == tot[i-1])
  69.                 c++;
  70.             else {
  71.                 res += c*1ll*c;
  72.                 c = 1;
  73.             }
  74.         }
  75.         res += c*1ll*c;
  76.         FOR(i,0,n) {
  77.             FOR(j,i+1,n) {
  78.                 if (a[i] == a[j]) {
  79.                     res -= sq[a[i]];
  80.                 } else {
  81.                     res -= cnt[a[i]]*1ll*cnt[a[j]];
  82.                 }
  83.             }
  84.         }
  85.         res /= 2;
  86.         FOR(i,0,b.size()) {
  87.             if (cnt[b[i]] >= 4) {
  88.                 LL now = cnt[b[i]] *1ll*(cnt[b[i]]  - 1);
  89.                 now *= (cnt[b[i]]  - 2);
  90.                 now *= (cnt[b[i]] - 3);
  91.                 now /= 24;
  92.                 res += now;
  93.             }
  94.         }
  95.         FOR(i,0,b.size()) {
  96.             FOR(j,i+1,b.size()) {
  97.                 LL now = cnt[b[i]] *1ll*(cnt[b[i]]  - 1);
  98.                 now *= cnt[b[j]];
  99.                 now *= (cnt[b[j]]  - 1);
  100.                 now /= 4;
  101.                 res += now;
  102.             }
  103.         }
  104.         cout<<res<<endl;
  105.  
  106. #ifdef Fcdkbear
  107.         double end = clock();
  108.         fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
  109. #endif
  110.         return 0;
  111. }
RAW Paste Data