SHARE
TWEET

Untitled

a guest Dec 8th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7. #define all(x) x.begin(), x.end()
  8.  
  9. template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
  10. template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
  11.  
  12.  
  13. const int MOD = 1000000009;
  14.  
  15. int add(int a, int b) {
  16.     a += b;
  17.     if (a >= MOD)
  18.         a -= MOD;
  19.     return a;
  20. }
  21.  
  22. const int MAXN = 110;
  23. int dp[MAXN][MAXN][MAXN];
  24.  
  25. int n, m, len;
  26.  
  27. void read() {
  28.     cin >> n >> m >> len;
  29.     if (len == 1) {
  30.         cout << 1 << endl;
  31.         exit(0);
  32.     }
  33. }
  34.  
  35. void run() {
  36.     for (int i = 0; i < MAXN; i++) {
  37.         for (int j = 0; j < MAXN; j++) {
  38.             for (int k = 0; k < MAXN; k++) {
  39.                 dp[i][j][k] = 0;
  40.             }
  41.         }
  42.     }
  43.     dp[0][0][0] = 1;
  44.  
  45.     for (int i = 0; i < m; i++) {
  46.         for (int pos_next = 1; pos_next + len - 1 <= n; pos_next++) {
  47.             dp[i + 1][pos_next][1] = add(dp[i + 1][pos_next][1], dp[i][0][0]);
  48.         }
  49.         if (i + len <= m) {
  50.             dp[i + len][0][0] = add(dp[i + len][0][0], dp[i][0][0]);
  51.         }
  52.  
  53.         for (int j = 1; j + len - 1 <= n; j++) {
  54.             for (int k = 1; k <= min(i, len - 1); k++) {
  55.                 if (dp[i][j][k] == 0) continue;
  56.                 int x = dp[i][j][k];
  57.                
  58.                 if (k + 1 < len)
  59.                     dp[i + 1][j][k + 1] = add(dp[i + 1][j][k + 1], x);
  60.                 else {
  61.                     dp[i + 1][0][0] = add(dp[i + 1][0][0], x);
  62.                 }
  63.                 if (i + len <= m)
  64.                     dp[i + len][j][k] = add(dp[i + len][j][k], x);
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. void write() {
  71.     cout << dp[m][0][0] << endl;
  72. }
  73.  
  74. signed main() {
  75.     ios_base::sync_with_stdio(0);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.     read();
  79.     run();
  80.     write();
  81.     return 0;
  82. }
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