【BZOJ4036】【LOJ2127】【HAOI2015】按位或

Author Avatar
q234rty 2月 25, 2018

Min-Max容斥+子集和变换即可。

下面不区分普通的数和集合。

设第一次访问第 i 位的时间为 X_i ，设 U 为 \{X_i\} ，则原题就是求 E(max(U)) 。 直接套用Min-Max容斥可得：

E(max(U))= \sum_{S \subseteq U} (-1)^{|S|+1}E(min(S))

考虑计算 E(min(S)) ，设

k=\sum_{T \subseteq {U-S}} P_T

由等比数列求和公式容易发现

E(min(S))=\frac{1}{1-k}

于是子集和变换求出所有的 k 即可，注意特判INF的情况。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=30000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9.     #ifdef LOCAL
  10.         freopen("4036.txt","r",stdin);
  11.     #endif
  12.     buf[fread(buf,1,MAXSIZE,stdin)]=' ';
  13.     bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17.     bool isneg;
  18.     int val=0;
  19.     for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20.     bufpos+=(isneg=buf[bufpos]=='-');
  21.     for(;isdigit(buf[bufpos]);bufpos++)
  22.         val=val*10+buf[bufpos]-'0';
  23.     return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27.     int val=0;
  28.     for(;!isdigit(buf[bufpos]);bufpos++);
  29.     for(;isdigit(buf[bufpos]);bufpos++)
  30.         val=val*10+buf[bufpos]-'0';
  31.     return val;
  32. }
  33. #endif
  34. char readchar(){
  35.     for(;isspace(buf[bufpos]);bufpos++);
  36.     return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39.     int cur=0;
  40.     for(;isspace(buf[bufpos]);bufpos++);
  41.     for(;!isspace(buf[bufpos]);bufpos++)
  42.         s[cur++]=buf[bufpos];
  43.     s[cur]='\0';
  44.     return cur;
  45. }
  46. double p[1<<20];
  47. char s[101];
  48. int main(){
  49.     init();
  50.     int n=readint();
  51.     for(int i=0;i<(1<<n);i++){
  52.         readstr(s);
  53.         p[i]=strtod(s,0);
  54.     }
  55.     for(int i=0;i<n;i++)
  56.         for(int j=0;j<(1<<n);j++)
  57.             if (j>>i&1)
  58.                 p[j]+=p[j^(1<<i)];
  59.     double ans=0;
  60.     for(int i=1;i<(1<<n);i++){
  61.         double t=1-p[(1<<n)-1-i];
  62.         if (t<1e-9)
  63.             return puts("INF"),0;
  64.         t=1/t;
  65.         if (__builtin_parity(i))
  66.             ans+=t;
  67.         else ans-=t;
  68.     }
  69.     printf("%.10f",ans);
  70. }

Written with StackEdit.

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/02/25/bzoj4036/

隐藏