Problem Link
type: dynamic programing, probability, expected value.
Solution:
...hmm, it feels good to be back after a long long break.
type: dynamic programing, probability, expected value.
Solution:
define, dp[i][j][b] = after performing the probabilistic OR on the 0-th to i-th number, what is the probability that, the j-th bit is b.
expected_value = 1*dp[n-1][0][1] + 2*dp[n-1][1][1] + ... 2^k * dp[n-1][k][1] + ...
...hmm, it feels good to be back after a long long break.
We don't actually need the third parameter b in the dp matrix.
ReplyDeletedp[i][j] can store after performing the probabilistic OR on the 0-th to i-th number, what is the probability that, the j-th bit is 1 [as here can be only two bits 0 or 1.]