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.
It's quite simple. If you analyse the brute dp, you'll see something like
dp[n][m] = sum ( dp[n-1][m-x*n] ) where 0<=x*n<=m
Start from smaller values, say n=2, and if you try to find the closed form, in terms of a formula for dp[2][m], you'll find that it depends on (m%2). Those having the same (m%2) have the same closed form.
Try for n=3, The closed form depends on various dp[2][m'] values, with gaps of 3 in m'. Hence it depends on (m%3), as well as dp[2][] values, essentially depending on (m%2) as well.
So, for general n,m. dp[n][m] has same closed form for m values such that they're the same modulo [1..n]. Which simply means the values of m, having the same modulo lcm[1..n] have similar closed forms, since there's a unique value of m modulo lcm[1..n] depending on individual moduli of m % [1..n]
Since n<=10 here, that means there are <=2520 distinct polynomials, and each one has degree <=10. So, you can do Lagrange interpolation to evaluate the polynomial at m, by giving it a n+1 different precomputed values of dp[n][m'] such that m' modulo lcm[1..n] = m modulo lcm[1..n].
Since there are only 2520 maximum different polynomials with degree <=10, your precomputation only requires 2520*10 values of m and 10 values of n, which is easily doable since brute dp is m*n.
I understand that dp[3][m] depends on m%3, but why does it also depend on m%2?
Consider each dp[2][m'] where m' takes values: m-3x such that 0<=x<=floor(m/3)
Here each dp[2][m'] will depend on m'%2, why do they also depend on m%2?
Because the dp[2][m'] values you get, the list is not similar for all m which are the same %3. Consider values m and m+3 for n=3, and try to find a closed form, you'll see they're different, because the m' values they get don't fall under the same class. On the other hand, m and m+6 will have the same closed form.
I'm sorry I can't explain it further, I guess you'll have to work a few values by hand and try to realize why this is happening. I didn't think this deep when I solved the problem, it was mostly intuition.
After thinking for a while, I realized that after dp[n][f(x)] reaches dp[n'][f2(x)] (where 3<=n, 2<=n'<n, f2(x) = f(x)-v1(n)-v2(n-1)-...-vk(n'+1)), since dp[n'][f2(x)] depends on f2(x)%n', we must make sure that f2(x)%n' doesn't depend on x.
Let's return to f2(x) for a while. f2(x) = f(x)-v1(n)-v2(n-1)-...-vk(n'+1). So, we know (v1(n)+v2(n-1)+...+vk(n'+1))%n' (it doesn't depend on x). But in order to make f2(x)%n' overall doesn't depend on x, f(x)%n' must not depend on x as well (coefficient of x in f(x) must be divisible by n'). So, coefficient of x must be divisible by each n' as well as n of course (that is, divisible by their LCM).