fork(1) download
copy 
  1. /*
  2.  *      Author: sparks
  3.  */
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long int ll;
  9. typedef unsigned long long ull;
  10.  
  11. #define ff first
  12. #define ss second
  13. #define pb push_back
  14. #define mkp make_pair
  15. #define pll pair<ll, ll>
  16. #define rep(i,n) for(i=0;i<n;i++)
  17. #define all(v) v.begin(), v.end()
  18.  
  19. void inp() {}
  20. template <typename T, typename... Args>
  21. void inp(T& n, Args&... args) //fast input function
  22. {
  23.   int ch=getchar(), sign=1; n=0;
  24.   while( ch < '0' || ch > '9' ) { if(ch=='-')sign=-1; ch=getchar(); }
  25.   while( ch >= '0' && ch <= '9' ) n = (n<<3)+(n<<1) + ch-'0', ch=getchar();
  26.   n=n*sign; inp(args...);
  27. }
  28.  
  29. #define MOD 1000000007
  30.  
  31. int main()
  32. {
  33.   ll i, n; inp(n);
  34.  
  35.   vector<ll> v;
  36.   map<ll, ll> m;
  37.   rep(i, n)
  38.   {
  39.     ll t; inp(t);
  40.     if(m.find(t) == m.end())
  41.     {
  42.       v.pb(0);
  43.       m[t] = v.size() - 1;
  44.     }
  45.     v[m[t]] += 1;
  46.   }
  47.  
  48.   ll x, y, z, e;
  49.   x = y = z = e = 1;
  50.  
  51.   rep(i, v.size())
  52.   {
  53.     ll t = 1;
  54.  
  55.     t += (3 * v[i]) % MOD;
  56.     t %= MOD;
  57.  
  58.     t += (3 * ((v[i] * v[i]) % MOD)) % MOD;
  59.     t %= MOD;
  60.  
  61.     x *= t;
  62.     x %= MOD;
  63.   }
  64.  
  65.   rep(i, v.size())
  66.   {
  67.     ll t = 1;
  68.  
  69.     t += (3 * v[i]) % MOD;
  70.     t %= MOD;
  71.  
  72.     t += (2 * ((v[i] * v[i]) % MOD)) % MOD;
  73.     t %= MOD;
  74.  
  75.     y *= t;
  76.     y %= MOD;
  77.   }
  78.  
  79.   y *= 3;
  80.   y %= MOD;
  81.  
  82.   rep(i, v.size())
  83.   {
  84.     ll t = 1;
  85.  
  86.     t += (3 * v[i]) % MOD;
  87.     t %= MOD;
  88.  
  89.     t += (1 * ((v[i] * v[i]) % MOD)) % MOD;
  90.     t %= MOD;
  91.  
  92.     e *= t;
  93.     e %= MOD;
  94.   }
  95.  
  96.   e *= 3;
  97.   e %= MOD;
  98.  
  99.   rep(i, v.size())
  100.   {
  101.     ll t = 1;
  102.  
  103.     t += (3 * v[i]) % MOD;
  104.     t %= MOD;
  105.  
  106.     z *= t;
  107.     z %= MOD;
  108.   }
  109.  
  110.   // cerr << x << ' ' << y << ' ' << z << endl;
  111.  
  112.   ll ans = 0;
  113.   ans += x; ans %= MOD;
  114.   ans -= y; ans += MOD; ans %= MOD;
  115.   ans += e; ans %= MOD;
  116.   ans -= z; ans += MOD; ans %= MOD;
  117.  
  118.   cout << ans << endl;
  119.   return 0;
  120. }
Time limit exceeded #stdin #stdout 5s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nmTHJo
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!