Advertisement
Fshl0

Untitled

Feb 15th, 2022
1,115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define pb push_back
  5.  
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace __gnu_pbds;
  9.  
  10. #define ordered_set tree<pair<ll,int>, null_type,less<pair<ll,int>>, rb_tree_tag,tree_order_statistics_node_update>
  11.  
  12. using namespace std;
  13. typedef long long ll;
  14.  
  15. const int MOD = 1e9 + 7;
  16. const int mxK = 1e5 + 9;
  17. const int mxN = 1e2 + 9;
  18. const int INF = 1e7 + 7;
  19. const double eps = 1e-7;
  20.  
  21. ll dp1[mxN][mxK], dp2[mxN][mxK], pre1[mxN][mxK], suff2[mxN][mxK], cnt[mxK];
  22.  
  23. void solve () {
  24.     int N, K;
  25.     cin >> N >> K;
  26.    
  27.     int n = sqrt (N);
  28.     for (int j = 1; j <= n; j++) {
  29.         int r = N / j;
  30.        
  31.         int l = ceil (N / (j + 1.0));
  32.         if (l * (j + 1) == N)
  33.             l++;
  34.        
  35.         cnt[j] = r - l + 1;
  36.         dp1[1][j] = 1;
  37.         dp2[1][j] = cnt[j];
  38.        
  39.         pre1[1][j] = pre1[1][j - 1] + dp1[1][j];
  40.     }
  41.    
  42.     for (int j = n; j >= 1; j--)
  43.         suff2[1][j] = suff2[1][j + 1] + dp2[1][j];
  44.        
  45.     for (int i = 2; i <= K; i++) {
  46.         for (int j = 1; j <= n; j++) {
  47.             dp1[i][j] = suff2[i - 1][j] + pre1[i - 1][n];
  48.             dp2[i][j] = pre1[i - 1][j] * cnt[j];
  49.            
  50.             pre1[i][j] = pre1[i][j - 1] + dp1[i][j];
  51.         }
  52.        
  53.         for (int j = n; j >= 1; j--)
  54.             suff2[i][j] = suff2[i][j + 1] + dp2[i][j];
  55.     }
  56.    
  57.     ll res = 0;
  58.     for (int j = 1; j <= n; j++) {
  59.         //cout << dp1[K][j] << ' ' << dp2[K][j] << "\n";
  60.        
  61.         res += dp1[K][j] + dp2[K][j];
  62.     }
  63.    
  64.     cout << res << "\n";
  65. }
  66.  
  67. int main () {
  68.     int t = 1;
  69.     //cin >> t;
  70.        
  71.     //preCalc ();
  72.     while (t--)
  73.         solve ();
  74.        
  75.     return 0;
  76. }
  77.  
  78. /*
  79.  ((2?3)?8)
  80.  1 1
  81.  
  82.  *
  83.  *
  84.  * */
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement