エイシングコン2020 D - Anything Goes to Zero (400)
最初の方針
一度操作を行うとpopcountの結果は$ n以下になる
事前に$ n以下の数での必要な操作回数を求めておく
$ dp[i] = dp[i \mod popcount(i) + 1]みたいになる
bit毎に初回のpopcountの計算をする
数が巨大になる場合があるのでbit毎に剰余を求めつつ足していく
全てのbitで全てのbitについて計算しているので$ O(N^2)になり間に合わない
次の方針
事前にpocountを1増減させた値で元のXについての結果を求めておく
全て0になる場合に注意
各bit毎にそこだけ新たに計算し直す
他のbitは上の事前計算の結果をそのまま利用できるので再計算不要
事前計算も各bitの再計算部分もそれぞれ$ O(N)なので全体で$ O(N)