AGC044-C Strange Dance
ある桁は自分より小さい桁に対して影響を及ぼさないので、操作後の下i桁目について、操作前の下i桁の数によってのみ決まる。
サルサが流れると、すべての桁が変わる。(0のときは変わらないが、変わると考えても困らないので変わると考える。)
サルサが2回流れると元に戻るので、圧縮できる場合がある。
ルンバが流れると、一番下の桁は変わる。また、下i桁目で繰り上がりが発生したときに下i+1桁目が変わる。
p(i,A)を、下i桁がAであって、ルンバによって下i桁目で繰り上がりが発生した時間の集合 と定義する。
操作前の下i桁がAで、操作後の下i桁目がどうなるかを考える。
ルンバによって下i桁目が変わるタイミングは、p(i-1,A % 3^(i-1))が分かっていると分かる。それらの間にあるサルサの数は累積和などで分かるので、シミュレーションにはp(i-1,A % 3^(i-1))回ぐらいかかる。
pのサイズの総和はO(N*|T|)なので間に合う。