fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/assoc_container.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. namespace std {
  9. #ifndef LOCAL
  10. #define cerr \
  11.   if (0) cerr
  12. #endif
  13.  
  14. struct custom_hash {
  15.   static uint64_t splitmix64(uint64_t x) {
  16.     // http://x...content-available-to-author-only...i.it/splitmix64.c
  17.     x += 0x9e3779b97f4a7c15;
  18.     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  19.     x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  20.     return x ^ (x >> 31);
  21.   }
  22.  
  23.   size_t operator()(uint64_t x) const {
  24.     static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  25.     return splitmix64(x + FIXED_RANDOM);
  26.   }
  27. };
  28. }  // namespace std
  29.  
  30. const int64_t MOD = 113127131137139149LL;
  31. const int N = 3e5 + 5;
  32.  
  33. int64_t add(int64_t a, int64_t b) {
  34.   a += b;
  35.   if (a >= MOD) a -= MOD;
  36.   if (a < 0) a += MOD;
  37.   return a;
  38. }
  39.  
  40. int64_t cal(int x) {
  41.   int64_t a = 2;
  42.   int64_t ans = 1;
  43.   while (x > 0) {
  44.     if (x & 1) {
  45.       ans = __int128_t(ans) * a % MOD;
  46.     }
  47.     a = __int128_t(a) * a % MOD;
  48.     x >>= 1;
  49.   }
  50.   return ans;
  51. }
  52.  
  53. int a[N];
  54. int64_t pref[N];
  55. int dp[N];
  56.  
  57. int32_t main() {
  58.   ios_base::sync_with_stdio(0);
  59.   cin.tie(0);
  60. #ifdef LOCAL
  61. #define task "a"
  62. #else
  63. #define task ""
  64. #endif
  65.   if (fopen(task ".inp", "r")) {
  66.     freopen(task ".inp", "r", stdin);
  67.     freopen(task ".out", "w", stdout);
  68.   }
  69.   int n;
  70.   cin >> n;
  71.   for (int i = 1; i <= n; i++) {
  72.     cin >> a[i];
  73.     pref[i] = (pref[i - 1] + cal(a[i])) % MOD;
  74.   }
  75.   vector<int64_t> cand;
  76.   for (int i = 1; i <= n; i++) {
  77.     int64_t cur = cal(a[i]);
  78.     for (int j = 0; (1 << j) <= n; j++) {
  79.       // pref[i] - ? = cur
  80.       // pref[i] - cur = ?
  81.       cand.emplace_back(cur);
  82.       cur += cur;
  83.       if (cur >= MOD) cur -= MOD;
  84.     }
  85.   }
  86.   sort(cand.begin(), cand.end());
  87.   cand.resize(unique(cand.begin(), cand.end()) - cand.begin());
  88.   gp_hash_table<int64_t, int> sum;
  89.   dp[0] = 1;
  90.   sum[pref[0]] = 1;
  91.   const int m = 1e9 + 7;
  92.  
  93.   for (int i = 1; i <= n; i++) {
  94.     int64_t cur = cal(a[i]);
  95.     for (auto cur : cand) {
  96.         int64_t need = pref[i] - cur; if (need < 0) need += MOD;
  97.       if (sum.find(need) != sum.end()) {
  98.         dp[i] += sum[need];
  99.         if (dp[i] >= m) dp[i] -= m;
  100.       }
  101.     }
  102.     sum[pref[i]] += dp[i];
  103.     if (sum[pref[i]] >= m) sum[pref[i]] -= m;
  104.   }
  105.   cout << dp[n];
  106.   return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
760342286
https://ideone.com/V3lAhw
language:
C++14 (gcc 8.3)
created:
2 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!