Guest User

Untitled

a guest
Dec 8th, 2019
95
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