fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long int llu;
  6. #define pb push_back
  7. #define mp make_pair
  8. #define X first
  9. #define Y second
  10. #define mem(a, v) memset(a, v, sizeof(a))
  11. #define PI acos(-1)
  12. #define S(a) scanf("%d",&a)
  13. #define SL(a) scanf("%lld",&a)
  14. #define S2(a, b) scanf("%d%d",&a,&b)
  15. #define nl printf("\n")
  16. #define deb(x) cout<<#x<<" : "<<x<<endl;
  17. #define deb2(x, y) cout<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl;
  18. #define deb3(x, y, z) cout<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl;
  19. #define debv(x) {cout<<#x<<" : "<<endl; for(int ii =0; ii < x.size(); ii++) cout<<x[ii]<<" "; cout<<endl; }
  20. #define debarr(x, xs) {cout<<#x<<" : "<<endl; for(int ii =0; ii < xs; ii++) cout<<x[ii]<<" "; cout<<endl; }
  21. //auto T=clock(); 
  22. //cout<<double(clock()-T)/CLOCKS_PER_SEC<<'\n';
  23. const ll mod = 1000000007LL;
  24. const int lmt = 1000005;
  25.  
  26. int cnt[lmt];
  27. int n, N = 0;
  28.  
  29. ll dp[lmt][2][2][2];
  30.  
  31. ll powr(int x, int y) {
  32. 	if(y == 0)
  33. 		return 1LL;
  34. 	ll tmp = powr(x, y/2);
  35. 	tmp = (tmp*tmp) % mod;
  36. 	if(y&1)
  37. 		tmp = (tmp*x) % mod;
  38. 	return tmp;
  39. }
  40.  
  41. ll solve(int idx, int ab, int bc, int ac) {
  42. 	if(idx > N) {
  43. 		if((ab == 1) && (bc == 1) && (ac == 1))
  44. 			return 1;
  45. 		return 0;
  46. 	}
  47. 	if(cnt[idx] == 0)
  48. 		return solve(idx+1, ab, bc, ac);
  49.  
  50. 	if(dp[idx][ab][bc][ac] != -1)
  51. 		return dp[idx][ab][bc][ac];
  52.  
  53. 	ll ans = solve(idx+1, ab, bc, ac);
  54.  
  55. 	ans %= mod;
  56.  
  57. 	ll mul = cnt[idx];
  58. 	ll mul1 = (3LL*mul) % mod;
  59.  
  60. 	ans += ((mul1*solve(idx+1, ab, bc, ac)) % mod);
  61. 	ans %= mod;
  62.  
  63. 	ll mul2 = (mul*mul) % mod;
  64.  
  65. 	ans += ((mul2*solve(idx+1, 1, bc, ac)) % mod);
  66. 	ans %= mod;
  67.  
  68. 	ans += ((mul2*solve(idx+1, ab, 1, ac)) % mod);
  69. 	ans %= mod;
  70.  
  71. 	ans += ((mul2*solve(idx+1, ab, bc, 1)) % mod);
  72. 	ans %= mod;
  73. 	return dp[idx][ab][bc][ac] = ans;
  74. }
  75.  
  76. int main(){
  77. 	mem(cnt, 0);
  78. 	mem(dp, -1);
  79. 	S(n);
  80. 	for(int i = 0; i < n; i++) {
  81. 		int x;
  82. 		S(x);
  83. 		N = max(N, x);
  84. 		cnt[x]++;
  85. 	}
  86.  
  87. 	ll ans = solve(1, 0, 0, 0);
  88. 	printf("%lld\n", ans);
  89.     return 0;
  90. }
Success #stdin #stdout 0.03s 69888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/yy6jr3
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!