Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <string>
- #include <algorithm>
- #include <iomanip>
- #include <map>
- #include <set>
- #include <bitset>
- #include <fstream>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- #define int long long
- #define eb emplace_back
- #define pb push_back
- #define ld long double
- #define f first
- #define s second
- #define dimas_pidoras true
- #define deb(a) cerr << #a << " = " << a << '\n';
- #define fast() { \
- ios_base::sync_with_stdio(0); \
- cin.tie(0); \
- cout << fixed << setprecision(20); \
- cerr << fixed << setprecision(11); \
- }
- const int INF = 1e9 + 7;
- const ld EPS = 1e-8;
- const int MAXI = 20000;
- const int MOD = 998244353;
- const int MAXST = 2000000;
- const int P = 40;
- const ld PI = 3.14159265358979323;
- ostream &operator<<(ostream &stream, const pair<int, int> &p) {
- stream << p.first << ' ' << p.second << ' ';
- return stream;
- }
- int dp[200][2];
- vector < vector < int > > v(100000);
- signed main() {
- #ifdef _LOCAL
- clock_t tStart = clock();
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- /* freopen("rollback.in", "r", stdin);
- freopen("rollback.out", "w", stdout);*/
- fast();
- int n, k, d;
- cin >> n >> k >> d;
- dp[0][0] = 1;
- /* первое число - число, которое мы разкладываем на множители
- второе число - 0: не использовали в разложениях числа >= d
- 1: использовали в разложениях числа >= d
- хранится в dp количетво разложений
- */
- for (int i = 1; i <= n; i++){
- for (int j = max(0LL, i - d + 1); j < i; j++) //добавляем к ответам число < d
- dp[i][0] += dp[j][0];
- for (int j = max(0LL, i - k); j < i; j++) //добавляем к ответам число <= k
- dp[i][1] += dp[j][1];
- for (int j = max(0LL, i - k); j <= i - d; j++) //добавляем к ответам число >= d и <= k
- dp[i][1] += dp[j][0];
- dp[i][0] %= INF; //берём по модулю (так как сказано в условии)
- dp[i][1] %= INF;
- }
- cout << dp[n][1] << '\n';
- #ifdef _LOCAL
- cerr << "Runtime: " << (ld)(clock() - tStart) / CLOCKS_PER_SEC << '\n';
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement