ABC194F

https://gyazo.com/1a17a7ce598564aed0e289ec0fd8e3cf

Thoughts.

The sample went through, but it's slow, and the TLE is not resolving.

That's a tough one, since "record if 16 different numbers are already available" would be 60,000~ and updated 2 x 10^5 times.

Official Explanation

I figured, "If I don't know what's already out there, I don't know if the number of numbers that have already appeared will increase the next time 1 appears, for example."

that is true

But since we are calculating 16 ways from 0 to F, even if we don't know which ones have already appeared, we can know "how many out of 16 will increase the number of appeared pieces".

Therefore, we only need to keep the number of numbers that have already appeared.

Post-Contest AC

code:py

def solve(N, K):

MOD = 1_000_000_007

D = 16 + 1

equal = 0

for digit in N:

digit = int(digit, 16)

for d in range(D):

if d == 0:

elif d != 16:

for new_digit in range(16):

if new_digit < digit:

new_d = equal

new_d += 1

if new_digit == 0 and equal == 0:

new_d = 0

for d in range(D):

less = new_less

equal += 1

if equal == K:

ret += 1

return ret % MOD

---