Advertisement
YEZAELP

o59_oct_c2_dslope

Dec 20th, 2021
756
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli Mod = 1e9 - 1;
  6. const int N = 8e4 + 10;
  7. const int K = 40 + 10;
  8. int ar[N];
  9. lli dp[N][K];
  10. int n, k;
  11.  
  12. void Upd(int i, int j, int val){
  13.     for(int idx=i;idx<=n;idx+=idx&-idx)
  14.         dp[idx][j] = (dp[idx][j] + (lli) val + Mod) % Mod;
  15. }
  16.  
  17. lli Sum(int i, int j, lli sum = 0){
  18.     for(int idx=i;idx>=1;idx-=idx&-idx)
  19.         sum = (sum + dp[idx][j] + Mod) % Mod;
  20.     return sum;
  21. }
  22.  
  23. int main(){
  24.  
  25.     scanf("%d %d", &n, &k);
  26.  
  27.     for(int i=1;i<=n;i++) scanf("%d", &ar[i]);
  28.  
  29.     for(int i=1;i<=n;i++){
  30.         Upd(ar[i], 1, 1);
  31.         for(int j=2;j<=k;j++){
  32.             lli sum = Sum(n, j - 1) - Sum(ar[i], j - 1);
  33.             Upd(ar[i], j, sum);
  34.         }
  35.     }
  36.  
  37.     cout << Sum(n, k);
  38.  
  39.     return 0;
  40. }
Advertisement
RAW Paste Data Copied
Advertisement