Advertisement
Arrias

Untitled

Jan 29th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <complex>
  3. #include <random>
  4. #include <cstdlib>
  5. #include <deque>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. const int mod = 1e9 + 7;
  11. int dp[5005][5005][2];
  12. int dp2[5005][5005][2];
  13.  
  14. void add(int &a, int b) {
  15. long long c = a;
  16. c += (long long)b;
  17. c %= mod;
  18. a = c;
  19. }
  20.  
  21. signed main()
  22. {
  23. int n, k;
  24. cin >> n >> k;
  25. if (n == k) {
  26. cout << 1;
  27. exit(0);
  28. }
  29. dp[k][k][1] = dp[k][k][0] = 1;
  30. for (int i = 1; i <= n; ++i)
  31. {
  32. if (i >= k) {
  33. dp2[k][i][0] = dp2[k][i][1] = 1;
  34. }
  35. }
  36. for (int sum = k + 1; sum <= n; ++sum)
  37. {
  38. for (int last = 1; last <= sum; ++last) {
  39. add(dp[sum][last][0], dp2[sum - last][last - 1][1]);
  40. int f = dp2[sum - last][sum][0] - dp2[sum - last][last][0];
  41. if (f < 0) f += mod;
  42. f %= mod;
  43. add(dp[sum][last][1], f);
  44. }
  45. int sm0 = 0;
  46. int sm1 = 0;
  47. for (int i = 1; i <= n; ++i) {
  48. add(sm0, dp[sum][i][0]);
  49. add(sm1, dp[sum][i][1]);
  50. dp2[sum][i][0] = sm0;
  51. dp2[sum][i][1] = sm1;
  52. }
  53. }
  54. int ans = 0;
  55. for (int last = 1; last <= n; ++last) {
  56. add(ans, dp[n][last][0]);
  57. add(ans, dp[n][last][1]);
  58. }
  59. cout << ans;
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement