I finished this problem over a month ago and never did my write up about it. I’d planned on doing a long discussion and go really deep into the math on it. But clearly that is too much for me to do right now.
I chose this problem because of the probability course I’m taking this term. I figured doing a couple problems based on probability would help me understand the material better. I enjoyed the chance to apply what I was learning. I would like to continue working on probability based problems.
I actually just turned in the final for my probability course and am feeling good about it. It was nice having a distraction from the difficult situation with the pandemic. Plus, I feel like the things I learned will be directly applicable to my job.
modulo = 10**8
def gcd(a, b):
while b:
a, b = b, a % b
return a
def reduce(a, b):
g = gcd(a, b)
return a//g, b//g
def p(n, k):
two_n_one = pow(2, n, modulo) - 1
two_n_k = pow(2, n - k, modulo)
return reduce(two_n_k*(k-1)*two_n_one + n*two_n_k, two_n_one**2)
def m(n, k):
num, den = p(n, k)
return num * den
def solve(n, k):
return m(n, k) % modulo
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
k = eval(sys.argv[2])
print(solve(n, k))
import pytest
from problem import solve, p, m
_test_p = (
((3, 1), (12, 49)),
((6, 2), (368, 1323)),
)
@pytest.mark.parametrize('n,expect', _test_p)
def test_p(n, expect):
assert expect == p(*n)
_test_m = (
((3, 1), 588),
((6, 2), 486864),
)
@pytest.mark.parametrize('n,expect', _test_m)
def test_m(n, expect):
assert expect == m(*n)
_test_solve = (
((10, 4), 24818624),
((99, 23), 80660992),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(*n)