fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #pragma GCC optimize("inline")
  3. #pragma GCC optimize("-fgcse")
  4. #pragma GCC optimize("-fgcse-lm")
  5. #pragma GCC optimize("-fipa-sra")
  6. #pragma GCC optimize("-ftree-pre")
  7. #pragma GCC optimize("-ftree-vrp")
  8. #pragma GCC optimize("-fpeephole2")
  9. #pragma GCC optimize("-ffast-math")
  10. #pragma GCC optimize("-fsched-spec")
  11. #pragma GCC optimize("-falign-jumps")
  12. #pragma GCC optimize("-falign-loops")
  13. #pragma GCC optimize("-falign-labels")
  14. #pragma GCC optimize("-fdevirtualize")
  15. #pragma GCC optimize("-fcaller-saves")
  16. #pragma GCC optimize("-fcrossjumping")
  17. #pragma GCC optimize("-fthread-jumps")
  18. #pragma GCC optimize("-funroll-loops")
  19. #pragma GCC optimize("fast-math")
  20. #pragma GCC optimize("-freorder-blocks")
  21. #pragma GCC optimize("-fschedule-insns")
  22. #pragma GCC optimize("inline-functions")
  23. #pragma GCC optimize("-ftree-tail-merge")
  24. #pragma GCC optimize("-fschedule-insns2")
  25. #pragma GCC optimize("-fstrict-aliasing")
  26. #pragma GCC optimize("-falign-functions")
  27. #pragma GCC optimize("-fcse-follow-jumps")
  28. #pragma GCC optimize("-fsched-interblock")
  29. #pragma GCC optimize("-fpartial-inlining")
  30. #pragma GCC optimize("no-stack-protector")
  31. #pragma GCC optimize("-freorder-functions")
  32. #pragma GCC optimize("-findirect-inlining")
  33. #pragma GCC optimize("-fhoist-adjacent-loads")
  34. #pragma GCC optimize("-frerun-cse-after-loop")
  35. #pragma GCC optimize("inline-small-functions")
  36. #pragma GCC optimize("-finline-small-functions")
  37. #pragma GCC optimize("-ftree-switch-conversion")
  38. #pragma GCC optimize("-foptimize-sibling-calls")
  39. #pragma GCC optimize("-fexpensive-optimizations")
  40. #pragma GCC optimize("inline-functions-called-once")
  41. #pragma GCC optimize("-fdelete-null-pointer-checks")
  42. #include<bits/stdc++.h>
  43. using namespace std;
  44. #define fi first
  45. #define se second
  46. #define ll long long
  47. #define el cout<<"\n"
  48. #define sz(x) (int)(x).size()
  49. #define all(x) (x).begin(),(x).end()
  50. #define f0(i,n) for(int i=0;i<n;i++)
  51. #define fl(i,n) for(int i=1;i<=n;i++)
  52. #define fz(i,a,n,z) for(int i=a;i<n;i+=z)
  53. #define rep(i,a,n,z) for(int i=a;i>n;i-=z)
  54. #define faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  55. #define file(name) freopen(name".inp","r",stdin);freopen(name".out","w",stdout);
  56. const int N = 2e5 + 5;
  57. const int maxn = 1e6 + 1;
  58. const int MOD = 1e9 + 7;
  59. int lt[25];
  60. void SinhLuyThua() {
  61.     lt[0] = 1;
  62.     for (int i = 1; i <= 20; ++i) {
  63.         lt[i] = lt[i - 1] * 2;
  64.     }
  65. }
  66. int A[N], T[N];
  67. int main() {
  68.     faster
  69.     SinhLuyThua();
  70.     int n;
  71.     cin >> n;
  72.     T[0] = 0;
  73.     for (int i = 1; i <= n; ++i) {
  74.         cin >> A[i];
  75.         T[i] = T[i - 1] + A[i];
  76.     }
  77.     ll res = 0;
  78.     if (n <= 5000) {
  79.         for (int i = 1; i <= n; ++i) {
  80.             for (int j = i; j <= n; ++j) {
  81.                 for (int k = 20; k >= 0; --k) {
  82.                     if ((T[j] - T[i - 1]) % lt[k] == 0) {res = res % MOD + lt[k] % MOD; break;}
  83.                 }
  84.             }
  85.         }
  86.     }
  87.     else
  88.     {
  89.         map<int, int> D;
  90.         int maxLuyThua = lower_bound(lt, lt + 20, T[n]) - lt;
  91.         if (T[n] < lt[maxLuyThua]) {
  92.             maxLuyThua--;
  93.         }
  94.         int cnt, m = 0;
  95.         for (int i = maxLuyThua; i >= 0; --i) {
  96.             D.clear();
  97.             D[0] = 1;
  98.             for (int j = 1; j <= n; ++j) {
  99.                 D[T[j] % lt[i]]++;
  100.             }
  101.             cnt = 0;
  102.             for (int j = 0; j < lt[i]; ++j) {
  103.                 cnt += D[j] * (D[j] - 1) / 2;
  104.             }
  105.             res += (cnt - m) * lt[i];
  106.             m = cnt;
  107.         }
  108.     }
  109.     cout << res;
  110.  
  111.  
  112. }
  113. /*-----------------------END-----------------------*/
  114.  
  115.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qKUnoR
language:
C++14 (gcc 8.3)
created:
12 days 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!