題目

這可算是描述很簡(jiǎn)單的一道題了！但是不簡(jiǎn)單。

\(S\)是一個(gè)可重集合，\(S = \{a_1, a_2, \dots, a_n \}\)。
等概率隨機(jī)取\(S\)的一個(gè)子集\(A = \{a_{i_1}, \dots, a_{i_m}\}\)。
計(jì)算出\(A\)中所有元素異或\(x\), 求\(x^k\)的期望。

要點(diǎn)

要點(diǎn) 1

所有異或出來(lái)的不同結(jié)果的數(shù)量是同樣多的（這句話可能有點(diǎn)不清楚）。
我的意思是說(shuō)，假如異或出來(lái)的結(jié)果有\(5\)、\(3\)、\(4\)，那么結(jié)果是\(5\)的異或方案數(shù)量是等于結(jié)果是\(3\)的異或方案數(shù)量的，也是等于結(jié)果是\(4\)的異或方案數(shù)量的。

除此之外，如果
設(shè)異或結(jié)果為\(0\)的子集（包括空集）數(shù)量為\(n\)，那么如果異或出來(lái)的結(jié)果有\(x\)，那么一定恰好有\(n\)種方案使得異或出來(lái)的結(jié)果是\(x\)。

要點(diǎn) 2 \(a_i\)的大小

設(shè)其大小為\(2^m-1\)，說(shuō)白了就是化成二進(jìn)制后有多少位。

那么\[(2^m-1)^k \leqslant answer < 2^{63}\]
即\[2^{mk} \leqslant 2^{63}\]
就是\[m \leqslant \frac {63} {k}\]

算法

算法 1

根據(jù)要點(diǎn)1，很容易想到高斯消元。消元后直接暴力即可，不過這個(gè)時(shí)間復(fù)雜度是 \(O(2^m)\)。只能通過\(60 \%\)的數(shù)據(jù)。

算法 2

設(shè)\(P = \lbrace a_1, a_2, \dots, a_{2^n} \rbrace\)，它的元素就是\(A\)中所有元素異或，所以它的大小為\(2^n\)。

那么答案為\[\frac {\sum_{i=1}^{2^n} {{a_i}^k}} {2^n}\]

由于\(a_i\)化成二進(jìn)制后位數(shù)比較少，所以用\(b_{i,j}\)表示\(a_i\)化成二進(jìn)制后的第\(j\)位。

那么答案可以寫成\[\frac {\sum_{i=1}^{2^n} ({{\sum_{j=0}^{m} { b_{i,j} \cdot 2^j }}})^k} {2^n}\]

現(xiàn)在假設(shè)\(k=2\)，有：\[\frac {\sum_{i=1}^{2^n} ({{\sum_{j=0}^{m} \sum_{p=0}^{m} {} { b_{i,j} \cdot b_{i,p} \cdot 2^{j+p} }}})} {2^n}\]

也就是：\[\sum_{j=0}^{m} \sum_{p=0}^{m}( \frac {\sum_{i=1}^{2^n} { b_{i,j} \cdot b_{i,p} }} {2^n}\cdot 2^{j+p})\]

對(duì)于\(\frac {\sum_{i=1}^{2^n} { b_{i,j} \cdot b_{i,p} }} {2^n}\)，是可以在\(O(n)\)的時(shí)間復(fù)雜度內(nèi)算出來(lái)的！如果\(j=p\)，那么這個(gè)值為第\(j\)為\(1\)的概率，如果\(j\neq p\)，那么這個(gè)值為第\(j\)和第\(p\)同時(shí)為\(1\)的概率，這個(gè)用一個(gè)迭代可以算出（根據(jù)要點(diǎn)1，算出最終所有可能出現(xiàn)的異或結(jié)果，這里的異或結(jié)果是指第\(j\)位和第\(p\)，只有4種結(jié)果）。

當(dāng)\(k \neq 2\)時(shí)，原理一樣！

這樣子，我們就可以在\(O(m^k \cdot (n + (2^k)^3))\)內(nèi)算出\(answer\)了。

km總復(fù)雜度(估算)

1	63	63
2	31	61504
3	21	4741632
4	15	207360000
5	12	8153726976

好吧，你會(huì)發(fā)現(xiàn)迭代的時(shí)間復(fù)雜度有點(diǎn)高！事實(shí)上可以利用高斯消元后的獨(dú)立數(shù)進(jìn)行推導(dǎo)同時(shí)出現(xiàn)\(1\)的概率。

這樣的話，時(shí)間復(fù)雜度就是\(O(m^k \cdot m)\)了。

轉(zhuǎn)載于:https://www.cnblogs.com/wangck/p/4187488.html

總結(jié)

以上是生活随笔為你收集整理的清华集训2014 day1 task1 玛里苟斯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。