Advertisement
kjmkj

Untitled

Jun 3rd, 2023
831
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define double long double
  6. #define pb push_back
  7. #define randGen mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
  8.  
  9. const int INF = 1e18;
  10. const int MOD = 1e9 + 7;
  11. map<int, int> a;
  12.  
  13. signed main() {
  14.   ios_base::sync_with_stdio(false);
  15.   cin.tie(NULL);
  16.   cout.tie(NULL);
  17.   int n;
  18.   cin >> n;
  19.   vector<int> sum[n + 1], sum1[n + 1];
  20.   for (int i = 0; i < n; ++i) {
  21.     int h;
  22.     cin >> h;
  23.     for (int j = 1; j * j <= h && j <= n; ++j) {
  24.       if (h / j <= n && h / j != j) {
  25.         sum[h / j].pb(i);
  26.       }
  27.       sum[j].pb(i);
  28.     }
  29.   }
  30.  
  31.   for (int i = 0; i < n; ++i) {
  32.     if (i > 0) {
  33.       sum1[1].pb(sum1[1].back() + 1);
  34.     } else {
  35.       sum1[1].pb(1);
  36.     }
  37.     sum1[1][sum1[1].size() - 1] %= MOD;
  38.   }
  39.   for (int i = 2; i <= n; ++i) {
  40.     for (int j = 0; j < sum[i].size(); ++j) {
  41.       auto it = lower_bound(sum[i - 1].begin(), sum[i - 1].end(), sum[i][j]);
  42.       int u = it - sum[i - 1].begin(), pl = 0;
  43.       if (u != 0) {
  44.         pl = sum1[i - 1][u - 1];
  45.       }
  46.       if (sum1[i].empty()) {
  47.         sum1[i].pb(pl % MOD);
  48.       } else {
  49.         sum1[i].pb(sum1[i].back() + pl);
  50.         sum1[i][sum1[i].size() - 1] %= MOD;
  51.       }
  52.     }
  53.   }
  54.   int suma = 0;
  55.   for (int i = 1; i <= n; ++i) {
  56.     if (sum1[i].empty()) {
  57.       continue;
  58.     }
  59.     suma += sum1[i].back();
  60.     suma %= MOD;
  61.   }
  62.   cout << suma % MOD;
  63.   return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement