fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #define ll long long
  5. #define ld long double
  6. #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
  7. #define mp make_pair
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define gcd __gcd
  12. #define lcm(a, b) (a*b)/gcd(a, b) 
  13. #define pcount __builtin_popcount 
  14. #define pcountll __builtin_popcountll
  15. #define nxtperm next_permutation
  16. //primitive roots: 998244353 - 3; 7340033 - 5
  17. //#pragma 03
  18. //#pragma GCC target ("sse4.2")
  19. const ll mod = 1000000007;
  20. const double PI = acos(-1.);
  21. using namespace std;
  22. using namespace __gnu_pbds;
  23. typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  24. typedef pair<int, int> ii;
  25. typedef vector<int> vi;
  26. typedef vector<ii> vii;
  27. typedef complex<double> cd;
  28.  
  29. ll n;  
  30. int lookup[20000050]; 
  31. // We have N <= 200000
  32. // Case 1: 1 <= N <= 2000: brute force o(n^2 log n). 
  33. // Case 2: 2000 < N <= 20000: lookup table
  34. // Case 3: FFT.  
  35.  
  36. void solvebrS()
  37. {
  38. 	int pre[20050], tmp, cnt = 0; pre[0] = 0; 
  39. 	for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp; 
  40. 	for(int i=1;i<=n;i++) 
  41. 		for(int j=0;j<i;j++) 
  42. 			lookup[pre[i] - pre[j]] = 1; 
  43. 	for(int i=1;i<=200000;i++) cnt += lookup[i];  
  44. 	cout << cnt - 1;
  45. }
  46.  
  47. void solvebrN()
  48. {
  49. 	int pre[2005], tmp; pre[0] = 0; 
  50. 	vector<ll> a;
  51. 	for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp; 
  52. 	for(int i=1;i<=n;i++) 
  53. 		for(int j=0;j<i;j++) 
  54. 			a.pb(pre[i] - pre[j]); 
  55. 	sort(a.begin(), a.end()); 
  56. 	int r = 0; 
  57. 	for(int i=1;i<a.size();i++) if(a[i] != a[i-1]) r++; 
  58. 	cout << r; 
  59. }
  60.  
  61. int rev[5000000];
  62. void fft(vector<cd> &a, int n, bool inv)
  63. {
  64. 	int lg = log2(n);
  65. 	for(int i=0;i<n;++i) 
  66. 	{
  67. 		rev[i] = (rev[i>>1] | ((i & 1) << lg)) >> 1;
  68. 		swap(a[i], (i<rev[i]?a[rev[i]]:a[i]));  
  69. 	}
  70. 	for(int l=2;l<=n;l<<=1)
  71. 	{
  72. 		double angle = 2 * PI / l * (inv ? -1 : 1); 
  73. 		cd wn(cos(angle), sin(angle)); 
  74. 		for(int i=0;i<n;i+=l)
  75. 		{
  76. 			cd w(1); 
  77. 			for(int j=0;2*j<l;j++) 
  78. 			{
  79. 				cd u = a[i+j], v = w * a[i+j+l/2]; 
  80. 				a[i+j] = u + v; 
  81. 				a[i+j+l/2] = u - v; 
  82. 				w *= wn; 
  83. 			}
  84. 		}
  85. 	}
  86. 	if(inv) for(auto &x:a) x /= n; 
  87. }
  88.  
  89. vector<int> mul(vector<cd> a, vector<cd> b)
  90. {
  91. 	vector<cd> a_ = a, b_ = b; 
  92. 	int n = 1, s = a.size() + b.size();
  93. 	while(n < s) n <<= 1; 
  94. 	a_.resize(n); 
  95. 	b_.resize(n);
  96. 	fft(a_, n, 0);
  97. 	fft(b_, n, 0);
  98. 	for(int i=0;i<n;i++) a_[i] *= b_[i]; 
  99. 	fft(a_, n, 1);
  100. 	vi ans(n); 
  101. 	for(int i=0;i<n;i++) ans[i] = round(a_[i].real()); 
  102. 	return ans;  
  103. }
  104.  
  105. void solve()
  106. {
  107. 	vector<cd> a, b;
  108. 	vector<int> pre; 
  109. 	a.assign(2000000, 0); 
  110. 	b.assign(2000000, 0); 
  111. 	pre.assign(200500, 0);
  112. 	int tmp; 
  113. 	for(int i=1;i<=n;i++) cin >> tmp, pre[i] = pre[i-1] + tmp; 
  114. 	b[pre[n]] = 1;
  115. 	for(int i=1;i<=n;i++) 
  116. 	{
  117. 		a[pre[i]] = 1; 
  118. 		b[pre[n] - pre[i]] = 1; 
  119. 	}
  120. 	vi C = mul(a, b);
  121. 	int ans = 0;  
  122. 	for(int i=pre[n]+1;i<C.size();i++) ans += (C[i]>0); 
  123. 	cout << ans-1; 
  124. }
  125.  
  126. signed main()
  127. {
  128. //	freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
  129. 	fast_cin();
  130. 	cin >> n; 
  131. 	if(n <= 2000) solvebrN(); 
  132. 	else if(n <= 20000) solvebrS(); 
  133. 	else solve(); 
  134. }
  135.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
9
6 1 7 3 7 1 8 5 7
stdout
copy 
28
https://ideone.com/lCIiqt
language:
C++14 (gcc 8.3)
created:
4 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!