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|)なので間に合う。