[Hard] VerySmoothDecompositions

16이하의 수들의 곱으로 나타내야 하므로 주어진 수 N은 N = 2^p2 * 3^p3 * 5^p5 * 7^p7 * 11^p11 * 13^p13 으로 나타낼 수 있어야 한다. 2, 3, 5, 7, 11, 13 으로 계속 나눠서 p2, p3, p5, p7, p11, p13 의 값을 구하고 다 나눈 뒤에도 1보다 큰 수가 남는다면 16이하의 수들의 곱으로는 나타낼 수 없다는 뜻이므로 답은 0이 된다. decomposition 에 나타나는 2의 개수를 a2, 3의 개수를 a3, 4의 개수를 a4, ... 라고 정의하면 p2 = a2 + 2*a4 + a6 + 3*a8 + a10 + 2*a12 + a14 + 4*a16 p3 = a3 + a6 + 2*a9 + a12 + a15 p5 = a5 + a10 + a15 p7 = a7 + a14 p11 = a11 p13 = a13 이 성립한다. 위의 식을 만족하는 {a2, a3, a4, ..., a16} 의 경우의 수를 구하는 문제로 바뀐다. 상태 공간의 일부를 brute force 로 결정하고 나머지를 잘 찾는 식으로 모든 경우의 수를 셀 수 있다. 여러가지 방법이 있을텐데 에디토리얼에 나와있는 방법을 설명하겠다. a11과 a13은 바로 결정이 되므로 관심에서 제외해도 된다. a15, a14, a10 을 각각 결정했다고 해보자. 우선, 식에 의해 a5, a7 의 값이 결정되고, 나머지 식을 정리하면 아래와 같다. p2 - a10 - a14 = a2 + 2*a4 + a6 + 3*a8 + 2*a12 + 4*a16 = x p3 - a15 = a3 + a6 + 2*a9 + a12 = y 남은 변수들로 2^x * 3^y 꼴의 수가 만들어진다. x*y 의 범위가 생각보다 작으므로 다음과 같은 DP를 생각할 수 있다. z = { 2, 3, 4, 6, 8, 9, 12, 16 } D[i][x][y] = z[1] ~ z[i] 의 수를 이용해 2^x * 3^y 꼴의 수를 만드는 경우의 수 = D[i-1][x][y] + D[i][x - (z[i]에 있는 2의 개수)][y - (z[i]에 있는 3의 개수)] 이 DP를 미리 계산해놓으면 a15, a14, a10 을 결정한 후, D[8][p2-a10-a14][p3-a15] 의 값을 답에 더하는 식으로 전체 경우의 수를 계산할 수 있다. x*y 의 범위를 구체적으로 생각해보자. x, y 는 2^x * 3^y <= D < 10^2500 x*log10(2) + y*log10(3) < 2500 를 만족한다. 이 때, x*y 가 최대가 되는 곳은 대략 x=4152, y=2620 쯤 이므로 위의 DP는 시간, 공간 제약 내에서 계산할 수 있다. a15, a14, a10 의 가능한 경우를 모두 다 살피기엔 그 경우의 수가 너무 많으므로 한가지 최적화가 더 필요하다. a15 를 먼저 결정하면 p3-a15 의 값이 결정된다. 따라서 D[8][i][p3-a15] 의 prefix sum 을 구해놓으면 이를 이용해 a10을 직접 결정하지 않고도 답을 계산할 수 있다.