Chlience

【题解】BZOJ 4036 [HAOI2015]按位或
Problem初始为 $0$ ,每一秒在 $[0,2^n-1]$ 中非等概率的选一个出来和当前数字异或,$i$ 被...
扫描右侧二维码阅读全文
25
2018/12

【题解】BZOJ 4036 [HAOI2015]按位或

Problem

初始为 $0$ ,每一秒在 $[0,2^n-1]$ 中非等概率的选一个出来和当前数字异或,$i$ 被选中的概率为 $p[i]$,问期望多久当前数字变为 $2^n-1$

Thought

看到这东西肯定是 $MIN-MAX$ 容斥了
将整体的期望最大值转化为子集的期望最小值

$$ MAX(S)=\sum_{T\in S}(-1)^{|T|+1}MIN(T) $$

先看下 $MIN(T)$ 怎么求

设对任意一个子集 $T$,被选中的概率为 $f(T)$
显然有

$$ f(T)=\sum_{X\cap T\neq\emptyset}p[X] $$

不太优美,考虑变形

$$ f(T)=1-\sum_{X\cap T=\emptyset}p[X]\\ f(T)=1-\sum_{X\subseteq \complement_ST}p[X]\\ 1-f(\complement_ST)=\sum_{X\subseteq T}p[X] $$

忽然发现右半边和 $FMT$ 形式相同,只需要求出来然后取个反就能计算出 $f(T)$ 的值

再观察 $MIN-MAX$ 容斥的式子,那个 $(-1)^{|T|+1}$ 看起来很难受,如果是 $(-1)^{|S-T|}$ 就好了,直接 $FMI$ 就完事了

由于这是 $-1$ 的次幂,所以只需要考虑奇偶性,也就是说,如果 $|S|$ 为偶数,则 $|S-T|$ 和 $|T|+1$ 奇偶性相反,反之 $|S-T|$ 和 $|T|+1$ 奇偶性相同,所以直接上 $FMI$ 然后分情况将答案乘上 $1$ 或者 $-1$ 即可

不要问我为啥不枚举子集,因为我懒

Code

#include <bits/stdc++.h>
using namespace std;
#define double long double
const double eps = 1e-6;
int n , N;
double p[1 << 20];
double f[1 << 20];
void FMT(double *p , int N) {
    for(int l = 1 ; l < N ; l <<= 1)
        for(int i = 0 ; i < N ; i += (l << 1))
            for(int j = i ; j < i + l ; ++ j)
                p[j + l] += p[j];
}
void FMI(double *p , int N) {
    for(int l = 1 ; l < N ; l <<= 1)
        for(int i = 0 ; i < N ; i += (l << 1))
            for(int j = i ; j < i + l ; ++ j)
                p[j + l] -= p[j];
}
int main() {
    scanf("%d" , &n); N = 1 << n;
    for(int i = 0 ; i < N ; ++ i)
        scanf("%llf" , &p[i]);
    FMT(p , N);
    for(int i = 1 ; i < N ; ++ i) {
        if(fabs(1.0 - p[N - i - 1]) < eps) {
            puts("INF");
            return 0;
        }
        f[i] = (n % 2 ? 1.0 : - 1.0) / (1.0 - p[N - i - 1]);
    }
    FMI(f , N);
    printf("%llf\n" , f[N - 1]);
    return 0;
}
Last modification:December 26th, 2018 at 07:32 pm

Leave a Comment