まず $n$ 個の数字を全部1としてみよう。そうすると、それぞれの数字は $\{0, 4, 9, 49\}$ とみなしてよい。

ここで4が9個以上あれば、それは9と0を使って書き換えることができるので、4の個数は[0, 8]とみなしていい。

例えば、4, 4, 4, 4, 4, 4, 4, 4, 4は9, 9, 9, 9, 0, 0, 0, 0, 0とすることで同じ個数で和を一定にできる。

同様の理由で9の個数も[0, 48]までと考えてよい。

あとは{4の個数, 9の個数}の各組が49で置き換えることができないなら、49を0個からおけるだけおけるパターンを考えればいいので、

$ans \leftarrow ans + n - (4の個数 + 8の個数) + 1$

とすればよい。

49に置き換えられるかどうかは愚直に4重ループを回してチェックしたらいい。

提出コード

まとめ

難しかった。なんか十分大きな数では線形に増えていくらしいけど、それはまだ良く分かってない