Product And Sum (SRM500 div1 1000)

問題

桁を全て足すとSになって、掛けるとになる数値の和を求めよ。
0<=p2,p3,p5,p7<=100
0<=S<=2500

解法

まず、どの数値をどのくらい使ってp2,p3,p5,p7を作るかを全探索する。p5,p7は5,7しかなく、p2,p3は4,6,8,9の数を決めれば一意に定まるので100^4/12弱ある。数値の数を決めたら、ある種類の数を1個固定したときに何通りの並べかえがあるかを計算する。これを全ての通りで1-9の数値で作られる数値の桁数で分類して総和をとる。最後に分類した総和を使い答えを計算する。TLEがきついので頑張らないと通らない。
答えを計算する際に並べ替えを使ってある桁にある数値がある場合の数を計算するのと、総和をとっておいて最後にまとめて計算するのがポイント。