Hi Codeforces,

Recently I am solving this problem from AtCoder Regular Contest 061: https://atcoder.jp/contests/arc061/tasks/arc061_d

However, I do not come up with any idea. I have tried to look at others' submissions since this contest does not have an English editorial, but I still cannot figure out what the mathematical formulas written in those codes mean.

Hope you guys can help me with the solution for this problem. Many thanks!

Every scenario can be represented by a string with

N+M+Kcharacters 'a', 'b' and 'c'. We should append one extra 'a' at the beginning (because Alice starts) and say that we want theN-th occurrence of 'a' to be earlier than theM-th andK-th occurrence of 'b' and 'c'.To get a quadratic solution, we can iterate over

BandC— the number of occurrences of 'b' and the number of occurrences of 'c' before theN-th occurrence of 'a'. Then use some binomials to get the answer.To make it faster,

I thinkwe should iterate over the sumB+C. Then some sum of binomial coefficients should be added to the answer, and maybe it's possible to compute it fast.Thank you, I will try to expand this idea!