fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define fo(i, n) for(int i = 1; i <= n; ++i)
  7.  
  8. typedef long long ll;
  9.  
  10. const int N = 500500;
  11. const int mod = 1e9 + 7;
  12.  
  13. int n, s, a[N];
  14. vector<int> d;
  15. int ans[N];
  16.  
  17. map<int, int> w;
  18.  
  19. inline int solve(int k) {
  20. int one = s / k, curs = 0, res = 0;
  21. w.clear();
  22. curs = w[0] = 0;
  23. for(int i = 1; i <= n; ++i) {
  24. curs += a[i];
  25. if(w.count(curs - one)) {
  26. w[curs] = w[curs - one] + 1;
  27. if(i < n && k - 1 == w[curs] || i == n && k == w[curs]) return 1;
  28. } else w[curs] = 0;
  29. }
  30. return 0;
  31. }
  32.  
  33. int main() {
  34.  
  35. ios::sync_with_stdio(0); cin.tie(0);
  36. cin >> n;
  37. fo(i, n) cin >> a[i], s += a[i];
  38. if(s == 0) {
  39. fo(i, n) cout << 1;
  40. return 0;
  41. }
  42. fo(i, n) a[i + n] = a[i];
  43. for(int i = 1; i * i <= s; ++i)
  44. if(s % i == 0) {
  45. d.pb(i);
  46. if(i * i != s) d.pb(s / i);
  47. }
  48. for(int one : d) {
  49. int k = s / one;
  50. if(k <= n) ans[k] = solve(k);
  51. }
  52. fo(i, n) cout << ans[i];
  53. return 0;
  54. }
Success #stdin #stdout 0s 4220KB
stdin
Standard input is empty
stdout
Standard output is empty