AtCoder Beginner Contest 255 E問題 Lucky Numbers
問題
提出解答
問題の概要
次を満たす長さ の整数列全体
の集合を
とする.
に対して,
となる.
に対して,
を
となる
以上
以下の整数の個数と定める.
このとき, を求めよ.
制約
解法1
実は次の定理が成り立つ.
定理 F.1.
を整数全体の集合とする. このとき,
を以下のようにして定めると,
は互いに逆写像になる. つまり,
の間には1対1対応がある.
を
の初項とする.
を初項が
であり,
の元であるような整数列とする.
証明は各整数 に対して,
が well-defined であること. つまり
を初項とし, 条件を満たすような整数列が唯一存在することを示せば良い. このとき, 和に関する条件を
の順に見ていくことにより,
と一意に定まる. 以降では とする.
この定理 F.1. から, 求めるべきは
としたときの,
.
であることがわかる.
としたとき, 整数
に対して,
である. これは は全て異なることから,
は以下と一致する.
- 二重添字数列
に登場する
の個数
よって, 各 の登場回数を辞書で記録し, その最大値を求めることにより, 計算量
で求めることができる.