2017-09-05 - HIR180's diary

めっちゃ良問だと思ったので書きます

問題概要

n個のbool値を受け取り1個のbool値を返す関数が与えられる。

この関数は「入力をflipすると出力もflipされる」が成り立っている。

今、n人の人間が3人の候補者に対しての3!=6通りの順序を独立にランダムに選ぶとき、

1人の候補者が他の2人に勝つような組み合わせは何通りあるか。

(2人の比較は各々の人間の(AをBよりも好むか)のbool値を関数に与えたときの出力が1ならA,0ならBとして定義される)

解法

答は、出力が1になるような2^(n-1)個のbitmaskのペア(重複を許す)に対し2^(一致している桁の個数)の総和を3倍した値。

計算において高速ゼータ変換の考え方を利用する。

dp[mask][i] = (上(n-i-1)bitがmaskに一致している値に対して、2^(下(i+1)bitでmaskと一致している桁の個数)の総和)

とすると、

dp[mask][i+1] = dp[mask][i]*2+dp[mask xor 2^i][i]

で求まる。