Hatena::Grouptopcoder

Hiro180の日記

 | 

2017-09-05

Codeforces Round #432 Div1 E Random Elections 13:28

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

問題概要

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]

で求まる。

まともな実装で14行とか http://codeforces.com/contest/850/submission/30090122

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Hiro180/20170905
 |