SHARE
TWEET

mwj2020el1b

a guest Dec 8th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* <copy-pasted-part> */
  2. #pragma GCC optimize("Ofast,fast-math,unroll-loops")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. #define int ll
  7. //#define double long double
  8. #define endl '\n'
  9. #define all(C) (C).begin(), (C).end()
  10. #define rall(C) (C).rbegin(), (C).rend()
  11. #define mp make_pair
  12. #define pb emplace_back
  13. #define dbg(x) cerr << #x << " : " << x << endl
  14. #define PI 3.14159265358979
  15.  
  16. using namespace std;
  17.  
  18. using ll = long long;
  19. using ull = unsigned long long;
  20. using ld = long double;
  21. using pii = pair <int, int>;
  22. using pld = pair <ld, ld>;
  23.  
  24. /*
  25. const ll MAX_MEM = 3e8;
  26. char MEM[MAX_MEM];
  27. ll MEM_POS = 0;
  28. void* operator new(size_t x)
  29. {
  30.     auto ret = MEM + MEM_POS;
  31.     MEM_POS += x;
  32.     assert(MEM_POS < MAX_MEM);
  33.     return ret;
  34. }
  35. void operator delete(void*)
  36. {}
  37. */
  38.  
  39. template <class T>
  40. istream& operator>> (istream &in, vector <T> &a)
  41. {
  42.     for (auto &i : a)
  43.         in >> i;
  44.     return in;
  45. }
  46.  
  47. template <class T>
  48. ostream& operator<< (ostream &out, vector <T> a)
  49. {
  50.     for (auto &i : a)
  51.         out << i << ' ';
  52.     return out;
  53. }
  54.  
  55. template <class T, class U>
  56. istream& operator>> (istream &in, pair <T, U> &p)
  57. {
  58.     in >> p.first >> p.second;
  59.     return in;
  60. }
  61.  
  62. template <class T, class U>
  63. ostream& operator<< (ostream &out, pair <T, U> p)
  64. {
  65.     out << p.first << " " << p.second << " ";
  66.     return out;
  67. }
  68.  
  69. inline void Start()
  70. {
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0), cout.tie(0);
  73.     //freopen("input.txt", "r", stdin);
  74.     //freopen("output.txt", "w", stdout);
  75. }
  76. /* </copy-pasted-part> */
  77.  
  78. const int P = 1e9 + 9;
  79. int add(int a, int b)
  80. {
  81.     return (a + b) % P;
  82. }
  83. int mul(int a, int b)
  84. {
  85.     return (a * b) % P;
  86. }
  87. struct comb
  88. {
  89.     vector <vector <int>> c;
  90.     comb() {}
  91.     comb(int n)
  92.     {
  93.         c.resize(n + 1, vector <int> (n + 1));
  94.         c[0][0] = 1;
  95.         for (int i = 1; i <= n; ++i)
  96.         {
  97.             for (int j = 0; j < n + 1; ++j)
  98.             {
  99.                 c[i][j] = add(c[i - 1][j], j ? c[i - 1][j - 1] : 0);
  100.             }
  101.         }
  102.     }
  103.     int operator() (int n, int k)
  104.     {
  105.         return c[n][k];
  106.     }
  107. };
  108. int solve(int n, int m, int k)
  109. {
  110.     vector <vector <int>> dp(m / k + 1, vector <int> (2));
  111.     dp[0][0] = 1;
  112.     dp[1][1] = 1;
  113.     dp[1][0] = n - k + 1;
  114.     comb c(2000);
  115.     dbg(c(18, 9));
  116.     for (int i = 2; i <= m / k; ++i)
  117.     {
  118.         for (int j = 0; j < i; ++j)
  119.             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)));
  120.         for (int j = 0; j < i; ++j)
  121.             dp[i][1] = add(dp[i][1], dp[j][0]);
  122.     }
  123.     return add(dp[m / k][0], dp[m / k][1]);
  124. }
  125.  
  126. signed main()
  127. {
  128.     Start();
  129.     int n, m, k;
  130.     cin >> n >> m >> k;
  131.     if (m % k != 0)
  132.     {
  133.         if (n != k)
  134.             return cout << 0, 0;
  135.         vector <int> dp(m + 1, 0);
  136.         dp[0] = 1;
  137.         for (int i = 1; i <= m; ++i)
  138.         {
  139.             dp[i] = add(dp[i - 1], (i - k >= 0 ? dp[i - k] : 0));
  140.         }
  141.         cout << dp[m];
  142.         return 0;
  143.     }
  144.     if (k == 1)
  145.         return cout << 1, 0;
  146.     if (k > n)
  147.     {
  148.         return cout << 1, 0;
  149.     }
  150.     cout << solve(n, m, k);    
  151.     return 0;
  152. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top