Here is the link of the problem: Bonus Money
My question is about sub-task 3. It is mentioned in the editorial of the problem that dp[n][r+xg] is a polynomial P(x) where g=lcm(1, 2, 3, ..., n) and 0 <= r < g. What is the general proof of this? And what is the significance of lcm(1, 2, 3, ..., n) that made the expression polynomial? (That is, it is said specifically that dp[n][r+xg] is a polynomial and not just dp[n][x]). I have referred to the comments on the editorial looking for a proof, but I have just found a small proof for only dp[1][x], dp[2][2x], dp[2][2x+1], dp[3][6x]. And not a general proof which generalizes to any n.
