fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define value first
  7. #define index second
  8.  
  9. #define EGRY                          \
  10.     ios_base::sync_with_stdio(false); \
  11.     cin.tie(NULL);
  12.  
  13. const int MAX = 105;
  14. const int MOD = 998244353;
  15. const int OO = INT_MAX;
  16.  
  17. const double EPS = (double)1e-9;
  18.  
  19. typedef pair<int, int> Point;
  20.  
  21. ll n, start_a, start_b, moves_a, moves_b;
  22.  
  23. ll add(ll a, ll b)
  24. {
  25.     return (((a % MOD) + (b % MOD)) % MOD);
  26. }
  27.  
  28. ll mul(ll a, ll b)
  29. {
  30.     return (((a % MOD) * (b % MOD)) % MOD);
  31. }
  32.  
  33. ll fast_power(ll base, ll power)
  34. {
  35.     if (power == 0)
  36.     {
  37.         return 1;
  38.     }
  39.  
  40.     ll p = fast_power(base, power / 2);
  41.  
  42.     ll res = mul(p, p);
  43.  
  44.     if (power % 2)
  45.     {
  46.         res = mul(res, base);
  47.     }
  48.  
  49.     return res;
  50. }
  51.  
  52. ll divide(ll up, ll down)
  53. {
  54.     return mul(up, fast_power(down, MOD - 2));
  55. }
  56.  
  57. ll mem[MAX][MAX][2];
  58.  
  59. ll dp(ll start_a, ll start_b, bool player)
  60. {
  61.  
  62.     if (start_a == n)
  63.     {
  64.         return (double)1;
  65.     }
  66.     if (start_b == n)
  67.     {
  68.         return (double)0;
  69.     }
  70.  
  71.     ll &ret = mem[start_a][start_b][player];
  72.  
  73.     if (ret != -1)
  74.     {
  75.         return ret;
  76.     }
  77.  
  78.     ll max_moves = (player == 0) ? moves_a : moves_b;
  79.  
  80.     ret = 0;
  81.  
  82.     for (int move = 1; move <= max_moves; move++)
  83.     {
  84.         if (player == 0)
  85.         {
  86.             ret = add(ret, divide(dp(min(start_a + move, n), start_b, !player), max_moves));
  87.         }
  88.         else
  89.         {
  90.             ret = add(ret, divide(dp(start_a, min(start_b + move, n), !player), max_moves));
  91.         }
  92.     }
  93.  
  94.     return ret;
  95. }
  96.  
  97. void solve()
  98. {
  99.  
  100.     cin >> n >> start_a >> start_b >> moves_a >> moves_b;
  101.  
  102.     bool player = 0;
  103.  
  104.     memset(mem, -1.0, sizeof(mem));
  105.  
  106.     cout << dp(start_a, start_b, 0);
  107. }
  108.  
  109. int main()
  110. {
  111.     EGRY
  112.         ll t = 1;
  113.     // cin >> t;
  114.  
  115.     while (t--)
  116.     {
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/bgi2OY
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!