fork download
copy 
  1. /*
  2. 	Vẫn là lối đi cũ: với những dạng bài đếm số đoạn con có tổng thoả tính chất X nào đó 
  3. 	thì ta thử đưa về công thức tổng tiền để xem thử, khi đó bài toán đưa về đếm số cặp (l, r) (l < r) 
  4. 	thoả mãn công thức Y nào đó. 
  5. 	Cụ thể ở bài này: 
  6. 	sum[l, r] chia hết cho n <=> (pref[r] - pref[l - 1]) chia hết cho n 
  7. 							 <=> (pref[r]) đồng dư (pref[l - 1]) (mod n) 
  8. 	nên bài toán đưa về đếm có bao nhiêu cặp (l, r) (l < r) sao
  9. 	cho pref[r] % n = pref[l] % n 
  10. */
  11.  
  12.  
  13. #include <bits/stdc++.h>
  14. using namespace std; 
  15.  
  16. typedef long long ll;  
  17.  
  18. const int N = 2e5 + 5;   
  19.  
  20. int n;   
  21. int a[N], pref[N];   
  22. int cnt[N];   
  23.  
  24. signed main() {
  25. 	ios::sync_with_stdio(0); cin.tie(0); 
  26. 	cin >> n;  
  27. 	for (int i = 1; i <= n; i++) {
  28. 		cin >> a[i];  
  29. 		pref[i] = (pref[i - 1] + a[i]) % n;    
  30. 		pref[i] = (pref[i] + n) % n; // pref[i] có thể âm nên phải chú ý 
  31. 	} 
  32.  
  33. 	// lưu ý: nếu x đủ nhỏ thì ta có thể tạo 1 mảng cnt[] để lưu tần suất của x
  34. 	//        nhưng trường hợp x khó để lưu vào 1 mảng (như x âm, hoặc x quá lớn) thì 
  35. 	//		  các em có thể nghĩ đến việc dùng map (map<int, int> cnt)  
  36.  
  37. 	ll ans = 0;  
  38.  
  39. 	for (int i = 0; i <= n; i++) {
  40. 		ans += cnt[pref[i]];   
  41. 		cnt[pref[i]]++;   
  42. 	}	
  43.  
  44. 	cout << ans << '\n';  
  45.  
  46. 	return 0;  
  47. }
  48.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5
3 1 2 7 4
stdout
copy 
1
https://ideone.com/IYgilf
language:
C++14 (gcc 8.3)
created:
1 year 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!