[Hard] ProductAndSum

조건을 만족하는 수 N의 digit 중 1의 개수를 d[1], 2의 개수를 d[2], ..., d[9] 라고 하자. (N의 digit에는 0이 있을 수 없으므로 d[0]은 의미없음) 전탐색을 하는데 신묘한 방식으로 경우의 수를 쳐낼 것이다. 일단 자명하게 d[5] = p5, d[7] = p7 이다. 먼저 d[6]을 고정한다. 그럼 d[8] <= (p2 - d[6]) / 3 , d[4] <= (p2 - d[6] - 3 * d[8]) / 2 , d[9] <= (p3 - d[6]) / 2 이다. 위의 범위 안에서 d[8], d[4], d[9]를 고정한다. 그럼 나머지가 다음과 같이 결정된다. d[2] = p2 - d[6] - 2 * d[4] - 3 * d[8] d[3] = p3 - d[6] - 2 * d[9] d[1] = S - (2 * d[2] + 3 * d[3] + 4 * d[4] + 5 * d[5] + 6 * d[6] + 7 * d[7] + 8 * d[8] + 9 * d[9]) (물론 d[1], d[2], d[3] >= 0 이어야 함) 이런 식으로 d[6], d[8], d[4], d[9] 를 잡는 경우의 수는 대략 8백만개 정도 된다. 다 돌려보면서 확인할 수 있다. 이제 d 수열을 결정했을 때 답을 O(1)에 구할 수 있으면 된다. 수의 길이 L = sum(d[i]) , 수의 가짓수 K = L! / (d[1]! * d[2]! * d[3]! * ... * d[9]!) 각 자리에 i가 등장하는 횟수는 K * (d[i] / L) 이므로 ( sum( i * d[i] ) * K / L ) * m 만큼 답에 더해주면 된다. ( m은 L자리의 1로 이루어진 수 ) 이를 O(1) 에 처리하기 위해서 팩토리얼, 역수 등을 전처리로 미리 구해놓자