Advertisement
Guest User

Untitled

a guest
Jun 13th, 2021
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define for0(i, n) for (ll i = 0; i < (int)(n); i++)
  5. #define for1(i, n) for (ll i = 1; i <= (int)(n); i++)
  6. #define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  7. #define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
  8. #define MOD 100000000
  9. #define inf 1e17
  10.  
  11. typedef long long ll;
  12.  
  13. void dk_98() {
  14. #ifndef ONLINE_JUDGE
  15.     freopen("input.txt", "r", stdin);
  16.     freopen("output.txt", "w", stdout);
  17. #endif
  18. }
  19.  
  20. int n1, n2, k1, k2;
  21. ll dp[101][2][11][101];
  22.  
  23. ll ways(int curr, int type, int succ, int type0) {
  24.     int type1 = curr - type0;
  25.     if (type0 > n1 or type1 > n2) return 0;
  26.     if ((type == 0 and succ > k1) or (type == 1 and succ > k2)) return 0;
  27.     if (type0 == n1 and type1 == n2) return 1;
  28.     if (dp[curr][type][succ][type0] != -1) return dp[curr][type][succ][type0];
  29.     if (type == 0) return dp[curr][type][succ][type0] = (ways(curr + 1, type, succ + 1, type0 + 1) + ways(curr + 1, 1 - type, 1, type0)) % MOD;
  30.     else return dp[curr][type][succ][type0] = (ways(curr + 1, type, succ + 1, type0) + ways(curr + 1, 1 - type, 1, type0 + 1)) % MOD;
  31. }
  32.  
  33. void solve() {
  34.     cin >> n1 >> n2 >> k1 >> k2;
  35.     memset(dp, -1, sizeof(dp));
  36.     ll term1 = ways(1, 0, 1, 1);
  37.     ll term2 = ways(1, 1, 1, 0);
  38.     cout << (term1 + term2) % MOD;
  39. }
  40.  
  41. int main() {
  42.     fast;
  43.     dk_98();
  44.     int t = 1; //cin >> t;
  45.     while (t--) {
  46.         solve();
  47.     }
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement