TopCoder/SRM500/ProductAndSum

出展 †

• TopCoder SRM500(Div1 Hard) (問題文)

問題 †

各桁の和がSかつ，積が 2^p2 * 3^p3 * 5^p5 * 7^p7 である正の整数をniceな数という．
与えられたS, p2, p3, p5, p7に対し，全てのniceな数の和を500500573で割った余りを求めなさい．

解法 †

• 制約条件は各数字を使う回数に対するもの
• なので，この問題で考えるべきポイントは以下の2つ
  • 制約条件を満たすような各数字iを使う回数siの組を求める
  • 各数字iをsi回ずつ使ってできる全ての数の和を求める

• 数字iを使う回数siについて，制約条件から以下の式が成り立つ
  • s0 = 0, s5 = p5, s7 = p7
  • s2 + 2*s4 + s6 + 3*s8 = p2
  • s3 + s6 + 2*s9 = p3
• s2, s3はs4, s6, s8, s9により決定することができる．
• s4, s6, s8, s9でループを回すと条件を満たすsiの組を列挙できる
  • 組の個数は最大ケースでも120万程度(実験値)
    

• 各数字iをsi回ずつ使ってできる全ての数の和を考える
  • はじめに，各桁を構成する全ての数字が区別できると考える．
  • このとき作れる数字は，構成する数字によるすべての順列．
  • この全ての数の筆算で各桁ごとに和を考えると，どの桁も和は(構成数字の和*(桁数-1)!)である．
    • 例)123なら123+132+213+231+312+321で，どの桁の和も(1+2+3)*(3-1)．
  • よって，この場合の総和は，(構成数字の和*(桁数-1)!)*(1を桁数分並べた数)になる．
  • 実際には同じ数字を区別しないので，これをs1からs9について，si!で割れば良い．

• 組の数が地味に多いので，総和計算の部分が遅いとTLEする．

回答 †

• ProductAndSum_pes.cpp - ↑解法準拠(pes)