Advertisement
Josif_tepe

Untitled

Nov 29th, 2021
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <cmath>
  6. using namespace  std;
  7. int n, k;
  8. int memo[1000][1000];
  9. vector<int> v [1000];
  10. int dp(int n_1, int predhoden){
  11.    if(n_1 == n){
  12.        return 1;
  13.    }
  14.    if(memo[n_1][predhoden] != -1){
  15.        return  memo[n_1][predhoden];
  16.    }
  17.    int mod = 1e9 + 7;
  18.    int res = 0;
  19.    for (int i = 0; i < v[predhoden].size(); i++) {
  20.        if(predhoden != v[predhoden][i] ){
  21.            res += dp(n_1 +1, v[predhoden][i] );
  22.            res = res% mod;
  23.        }
  24.    }
  25.    return memo[n_1][predhoden] = res;
  26. }
  27. int main(){
  28.    cin >> n >> k;
  29.    int res = 0;
  30.    for (int i = 0; i < 1000; i++) {
  31.        for (int j = 0; j < 1000; j++) {
  32.            memo[i][j]= -1;
  33.        }
  34.    }
  35.    for (int i = 1; i <= k; i++) {
  36.        for (int j = 1; j <= k; j++) {
  37.            if(i%j  == 0 || j%i == 0){
  38.                v[i].push_back(j);
  39.            }
  40.        }
  41.    }
  42.     int mod = 1e9 + 7;
  43.    for (int i = 1; i <= k; i++) {
  44.        res += dp(1,i);
  45.        res %= mod;
  46.    }
  47.    cout << res << endl;
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement