(n-ary) Gray code と累積和・階差
Prefix sum - Wikipedia, the free encyclopediaより。
なんでもGray codeの逆変換 = Z/2Z上の累積和で、つまりGray code変換 = 階差らしい。
Gray code - Wikipedia, the free encyclopediaにあるgeneralizeのn-ary Gray codeも同じようにZ/nZ上の階差・累積和となる(おそらくは)。
この考えの競プロ的使い方としては、累積和法させる時にGray codeを出して累積和法であることを「隠す」ことくらいかな。まあ既にあるかもしれないけど。
余談だが累積和(cumlative sum)ってprefix sum(接頭辞和という訳が少し見つかった)とも言うんだね。LCAといい、こういう複数の呼び方があるやつどうにかしてほしい…
