I recently upsolved [C. Gellyfish and Eternal Violet](https://mirror.codeforces.com/contest/2115/problem/C) with this [submission](https://mirror.codeforces.com/contest/2115/submission/342134008), which resulted in an AC verdict.↵
↵
But I am concerned about this part of my code:↵
↵
~~~~~↵
double ans = 0, last = 1;↵
for(int i = 1; i <= s; i++) last *= q;↵
for(int i = s; i <= r; i++) {↵
ans += last * dp0[r-i][max(1,m-i+s)];↵
last *= p * i / (i+1-s);↵
}↵
cout << ans << endl;↵
~~~~~↵
↵
Basically, `last` is just a probability representing the current binomial distribution: $\binom{i-1}{s-1}\,p^{i-s}\,q^{s}$.↵
↵
I initially computed the probability of `last` with $i=s$, which is just $\binom{s-1}{s-1}\,p^{0}\,q^{s}$, before starting the second loop and transitioning it to the next value of $i$ every cycle.↵
↵
What I'm worried about here is that $q^s$ can be very small (effectively as small as $0.01^{4000}$ under the constraints of the problem).↵
↵
This can be problematic since I'm working with `double`, which makes me question if there is a hack that can break my solution.↵
↵
Assuming there is a hack that breaks my solution, how can I compute `last` to avoid running into problems with floating-point underflow?
↵
But I am concerned about this part of my code:↵
↵
~~~~~↵
double ans = 0, last = 1;↵
for(int i = 1; i <= s; i++) last *= q;↵
for(int i = s; i <= r; i++) {↵
ans += last * dp0[r-i][max(1,m-i+s)];↵
last *= p * i / (i+1-s);↵
}↵
cout << ans << endl;↵
~~~~~↵
↵
Basically, `last` is just a probability representing the current binomial distribution: $\binom{i-1}{s-1}\,p^{i-s}\,q^{s}$.↵
↵
I initially computed the probability of `last` with $i=s$, which is just $\binom{s-1}{s-1}\,p^{0}\,q^{s}$, before starting the second loop and transitioning it to the next value of $i$ every cycle.↵
↵
What I'm worried about here is that $q^s$ can be very small (effectively as small as $0.01^{4000}$ under the constraints of the problem).↵
↵
This can be problematic since I'm working with `double`, which makes me question if there is a hack that can break my solution.↵
↵
Assuming there is a hack that breaks my solution, how can I compute `last` to avoid running into problems with floating-point underflow?
