Advertisement
FreakSkipper

Untitled

Mar 4th, 2021
1,331
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. // https://codeforces.com/group/JC4gmpF4LH/contest/259112/problem/T
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define vi vector<int>
  7. #define vll vector<ll>
  8. #define ll long long
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define mp make_pair
  12. #define ii pair<int, int>
  13. #define ff first
  14. #define ss second
  15.  
  16. #define PRIME 1000000007
  17.  
  18. // value, pos
  19. int t[2005][2005];
  20.  
  21. int f(vi &a, size_t i, int n) {
  22.     if (n <= 0) return 0;
  23.     if (i == a.size()) return 1;
  24.  
  25.     if (t[a[i]][i]) return t[a[i]][i];
  26.  
  27.     int ans = 0;
  28.     int pre = a[i];
  29.  
  30.     for (int j = 1; j <= n; j++) {
  31.         int aux;
  32.         if (i > 0) {
  33.             aux = a[i - 1] * j;
  34.         } else {
  35.             aux = j;
  36.         }
  37.  
  38.         if (aux <= n) {
  39.             a[i] = aux;
  40.             ans = (ans + f(a, i + 1, n)) % PRIME;
  41.         } else
  42.             break;
  43.     }
  44.    
  45.     t[a[i]][i] = ans;
  46.     a[i] = pre;
  47.  
  48.     return ans;
  49. }
  50.  
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(NULL);
  54.  
  55.     int n, k;
  56.     cin >> n >> k;
  57.  
  58.     memset(t, 0, sizeof(t));
  59.  
  60.     vi v(k);
  61.     fill(v.begin(), v.end(), 1);
  62.  
  63.     int ans = f(v, 0, n);
  64.  
  65.     cout << ans << endl;
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement