Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* <copy-pasted-part> */
- #pragma GCC optimize("Ofast,fast-math,unroll-loops")
- #include <bits/stdc++.h>
- #define int ll
- //#define double long double
- #define endl '\n'
- #define all(C) (C).begin(), (C).end()
- #define rall(C) (C).rbegin(), (C).rend()
- #define mp make_pair
- #define pb emplace_back
- #define dbg(x) cerr << #x << " : " << x << endl
- #define PI 3.14159265358979
- using namespace std;
- using ll = long long;
- using ull = unsigned long long;
- using ld = long double;
- using pii = pair <int, int>;
- using pld = pair <ld, ld>;
- /*
- const ll MAX_MEM = 3e8;
- char MEM[MAX_MEM];
- ll MEM_POS = 0;
- void* operator new(size_t x)
- {
- auto ret = MEM + MEM_POS;
- MEM_POS += x;
- assert(MEM_POS < MAX_MEM);
- return ret;
- }
- void operator delete(void*)
- {}
- */
- template <class T>
- istream& operator>> (istream &in, vector <T> &a)
- {
- for (auto &i : a)
- in >> i;
- return in;
- }
- template <class T>
- ostream& operator<< (ostream &out, vector <T> a)
- {
- for (auto &i : a)
- out << i << ' ';
- return out;
- }
- template <class T, class U>
- istream& operator>> (istream &in, pair <T, U> &p)
- {
- in >> p.first >> p.second;
- return in;
- }
- template <class T, class U>
- ostream& operator<< (ostream &out, pair <T, U> p)
- {
- out << p.first << " " << p.second << " ";
- return out;
- }
- inline void Start()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0), cout.tie(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- }
- /* </copy-pasted-part> */
- const int P = 1e9 + 9;
- int add(int a, int b)
- {
- return (a + b) % P;
- }
- int mul(int a, int b)
- {
- return (a * b) % P;
- }
- struct comb
- {
- vector <vector <int>> c;
- comb() {}
- comb(int n)
- {
- c.resize(n + 1, vector <int> (n + 1));
- c[0][0] = 1;
- for (int i = 1; i <= n; ++i)
- {
- for (int j = 0; j < n + 1; ++j)
- {
- c[i][j] = add(c[i - 1][j], j ? c[i - 1][j - 1] : 0);
- }
- }
- }
- int operator() (int n, int k)
- {
- return c[n][k];
- }
- };
- int solve(int n, int m, int k)
- {
- vector <vector <int>> dp(m / k + 1, vector <int> (2));
- dp[0][0] = 1;
- dp[1][1] = 1;
- dp[1][0] = n - k + 1;
- comb c(2000);
- dbg(c(18, 9));
- for (int i = 2; i <= m / k; ++i)
- {
- for (int j = 0; j < i; ++j)
- dp[i][0] = add(dp[i][0], mul(mul(add(dp[j][1], dp[j][0]), (n - k + 1)), c(k + i - j - 3, k - 2)));
- for (int j = 0; j < i; ++j)
- dp[i][1] = add(dp[i][1], dp[j][0]);
- }
- return add(dp[m / k][0], dp[m / k][1]);
- }
- signed main()
- {
- Start();
- int n, m, k;
- cin >> n >> m >> k;
- if (m % k != 0)
- {
- if (n != k)
- return cout << 0, 0;
- vector <int> dp(m + 1, 0);
- dp[0] = 1;
- for (int i = 1; i <= m; ++i)
- {
- dp[i] = add(dp[i - 1], (i - k >= 0 ? dp[i - k] : 0));
- }
- cout << dp[m];
- return 0;
- }
- if (k == 1)
- return cout << 1, 0;
- if (k > n)
- {
- return cout << 1, 0;
- }
- cout << solve(n, m, k);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement