G: XOR Duplication

全体FA: askr_58 (10:35)

オンサイトFA: Maximum_Bandaisan: (21:20)

AC: 21/22

原案: amesyu

問題概要

以下の操作をK回行ったあとの値の総和を求めよ。

操作前に書かれているすべての値に対して同時に行う。�xが黒板に書かれていた時、x xor 1, … , x xor Nを新たに書く。

• 2 ≤ N ≤ 2×10⁵
• 0 ≤ K ≤ 10⁹

​

解法1

各ビット毎に独立に考えるてみるとiビット目に対して、

0 ~ Nでの範囲でiビット目が0である個数、1である個数が分かればDPが立てられる。O(KlogN)

-> これは行列累乗で高速化可能。

​

解法1

0 ~ Nのうちiビット目が0である個数をa、1である個数をbとするとxorの操作は以下の行列Aで表すことができる。

後はこの行列をK乗して、1の成分の個数に2ⁱを掛ける

各ビット毎にやるので O(logNlogK) で十分に高速

解法2

​

アダマール変換(Xor Convolution) でぶん殴る。O(NlogK)