1 前言

大概又是Min-Max容斥與FMT的裸題吧
剛學(xué)完Min-Max容斥，式子推的飛快

2 題目相關(guān)

2.1 題目大意

一開始你手上有一個(gè)數(shù)$0$，每次或上隨機(jī)一個(gè)在$[0,2^n)$中的數(shù)（給出隨到每個(gè)數(shù)的概率），求期望多少步你手上的數(shù)變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$2^n?1$

2.2 數(shù)據(jù)范圍

$n\le 20$，所有概率的輸入以及期望步數(shù)的輸出都使用實(shí)數(shù)

3 題解

我們發(fā)現(xiàn)我們可以直接Min-Max容斥
$$max\{S\}=\sum _{T?S}(?1{)}^{|T|+1}min\{T\}$$
我們發(fā)現(xiàn)$max\{S\}$相當(dāng)于是變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$2^n?1$的期望步數(shù)，$min\{T\}$代表進(jìn)行操作與集合$T$有交的期望步數(shù)
我們就可以直接做了
我們知道，如果求出了$min\{T\}$我們可以直接$\Theta (2^n)$計(jì)算答案了
考慮如何計(jì)算$min\{T\}$
設(shè)取到$S$的概率為$g_S$，我們發(fā)現(xiàn)$$min\{S\}=\frac{1}{1?{\sum }_{T\cap S=?}{g}_T}$$
我們相當(dāng)于要求$$\begin{array}{rl}{f}_S& =\sum _{T\cap S=?}{g}_T\\ f_S& =\sum _{T\cap (C{u}_S)=T}{g}_T\\ f_S& =\sum _{T?(C{u}_S)}{g}_T\end{array}$$
然后翻轉(zhuǎn)一下，就是子集卷積了，使用FMT即可
非常方便

4 代碼

貼上我寫的第一份代碼（未卡常版本）

#include<cstdio> #include<cctype> #include<algorithm> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } double xs[11][10]; template <typename T> inline void Read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(cu=='.'){cu=getchar();int t=0;while(isdigit(cu))x+=xs[++t][cu-'0'],cu=getchar();}if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } int bit[21],n,lenth; double g[2097152],ans; bool pc[2097152]; int main() {xs[0][1]=1;for(rg int i=1;i<=10;i++){xs[i][1]=xs[i-1][1]/10;for(rg int j=1;j<=9;j++)xs[i][j]=xs[i][1]*j;}bit[0]=1;for(rg int i=1;i<=20;i++)bit[i]=bit[i-1]<<1;read(n),lenth=bit[n];for(rg int i=lenth-1;i>=0;i--)Read(g[i]);for(rg int i=1;i<lenth;i<<=1)for(rg int j=0;j<lenth;j+=(i<<1))for(rg int k=0;k<i;k++)g[j+k]+=g[j+k+i];const int Low=lenth-1;for(rg int i=1;i<lenth;i++){pc[i]=pc[i>>1]^(i&1);if(g[i]>=0.999999999){puts("INF");return flush(),0;}if(pc[i])ans+=1.0/(1-g[i]);else ans-=1.0/(1-g[i]);}printf("%.8lf",ans);return flush(),0; }

5 總結(jié)

這道題我進(jìn)行了一波卡常（你看我寫的第一份代碼已經(jīng)用實(shí)數(shù)讀優(yōu)了）
然后我學(xué)習(xí)到了一個(gè)小技巧
這題里的FMT我用的是FWTand的寫法（寫FWTor也可以，反正不是兩重循環(huán)的）
然后對于FWT，將最底下的兩層單獨(dú)提出來用for循環(huán)做，速度會有明顯的提升
就不貼卡常后的代碼了

總結(jié)

以上是生活随笔為你收集整理的[HAOI2015][loj2127]按位或的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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