Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <string>
  5. #include <algorithm>
  6. #include <iomanip>
  7. #include <map>
  8. #include <set>
  9. #include <bitset>
  10. #include <fstream>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13.          
  14. using namespace std;
  15.  
  16.    
  17. #pragma GCC optimize("Ofast")
  18. #pragma GCC optimize("no-stack-protector")
  19. #pragma GCC optimize("unroll-loops")
  20. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  21. #pragma GCC optimize("fast-math")
  22.      
  23. #define int long long
  24. #define eb emplace_back
  25. #define pb push_back
  26. #define ld long double
  27. #define f first
  28. #define s second
  29. #define dimas_pidoras true
  30. #define deb(a) cerr << #a << " = " << a << '\n';
  31. #define fast() { \
  32.     ios_base::sync_with_stdio(0); \
  33.     cin.tie(0); \
  34.     cout << fixed << setprecision(20); \
  35.     cerr << fixed << setprecision(11); \
  36. }
  37.  
  38. const int INF = 1e9 + 7;
  39. const ld EPS = 1e-8;
  40. const int MAXI = 20000;
  41. const int MOD = 998244353;
  42. const int MAXST = 2000000;
  43. const int P = 40;
  44. const ld PI = 3.14159265358979323;
  45.        
  46. ostream &operator<<(ostream &stream, const pair<int, int> &p) {
  47.     stream << p.first << ' ' << p.second << ' ';
  48.     return stream;
  49. }
  50.  
  51.  
  52. int dp[200][2];
  53. vector < vector < int > > v(100000);
  54.  
  55.  
  56. signed main() {
  57. #ifdef _LOCAL              
  58.     clock_t tStart = clock();
  59.     freopen("input.txt", "r", stdin);
  60.     freopen("output.txt", "w", stdout);
  61. #endif
  62.    /* freopen("rollback.in", "r", stdin);
  63.     freopen("rollback.out", "w", stdout);*/
  64.     fast();
  65.  
  66.     int n, k, d;
  67.     cin >> n >> k >> d;
  68.     dp[0][0] = 1;
  69.     /*  первое число - число, которое мы разкладываем на множители
  70.         второе число -  0: не использовали в разложениях числа >= d
  71.                         1: использовали в разложениях числа >= d
  72.         хранится в dp количетво разложений
  73.     */
  74.     for (int i = 1; i <= n; i++){
  75.         for (int j = max(0LL, i - d + 1); j < i; j++) //добавляем к ответам число < d
  76.             dp[i][0] += dp[j][0];
  77.         for (int j = max(0LL, i - k); j < i; j++) //добавляем к ответам число <= k
  78.             dp[i][1] += dp[j][1];
  79.         for (int j = max(0LL, i - k); j <= i - d; j++) //добавляем к ответам число >= d и <= k
  80.             dp[i][1] += dp[j][0];
  81.         dp[i][0] %= INF; //берём по модулю (так как сказано в условии)
  82.         dp[i][1] %= INF;
  83.     }
  84.     cout << dp[n][1] << '\n';
  85.  
  86. #ifdef _LOCAL
  87.     cerr << "Runtime: " << (ld)(clock() - tStart) / CLOCKS_PER_SEC << '\n';
  88. #endif  
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement