メモ

yukicoderでゆるふわgolf

a+b=a^b+2(a&b)の一般化

bit毎の排他的論理和を \oplus、論理積を \odot と置くと、
任意の非負整数 a, b に対して
a+b=a\oplus b+2(a \odot b)
が成り立ちます。
これは
0\oplus 0+2(1\odot 1)=0+0=0\\ 1\oplus 1+2(1\odot 1)=0+2=2\\ 0\oplus 1+2(0\odot 1)=1+0=1
を観察すれば成り立つことが示せます。
この等式は競技プログラミングで非常によく使われるテクニックの一つです。
Yukiちゃんはこの等式を一般化して、
\displaystyle x_1+x_2+\cdots+x_N=\sum_{k=1}^{N}a_k\sigma_k

の形で表せないか気になりました。ここで \sigma_k は \oplus ,\odot を演算とする x_1,x_2,\ldots,x_N の k 次対称式です。
例えば、N=3 のときは、
\displaystyle x_1+x_2+x_3=a_1(x_1\oplus x_2\oplus x_3)+a_2(x_1\odot x_2\oplus x_2\odot x_3\oplus x_3\odot x_1)+a_3(x_1\odot x_2\odot x_3)
です。
実は帰納法により、
\displaystyle x_1+x_2+\cdots+x_N=\sigma_1+2\sigma_2+4\sigma_4+8\sigma_8+16\sigma_{16}+\cdots
であることが示せます。

37zigen.com