ABC 122 D - We Like AGC

• 問題
• AC

メモ化で書いていたら混乱したのでボトムアップのDPで書き直した。あとで解き直すかも。

昔の AtCoder (りんごさん体制になる前) だったら D で N <= 10^18 という問題が旧 ARC の後半で出せたと思いますが、今だったらそういう独自性のないテンプレ問題は AGC どころか ARC でも即 reject ですね…現状の AtCoder の問題点の一つはビギナーを卒業した人の「お勉強」に適さないことです。

— えびま (@evima0) 2019年3月24日

（高々）64次元空間の線型変換とみなせるのか。なるほどー…… 言われてみればとなるけど、これを${\mathcal O}(\log n)$で解けと言われたら今の自分には普通のDPすら見えなくなりそう。