【CF582E】Boolean Function

題意：給你一個(gè)長(zhǎng)度為n的表達(dá)式，其中未知數(shù)有A,B,C,D和？，運(yùn)算有&和|和?（表達(dá)式中用括號(hào)確定了唯一的運(yùn)算順序）。?代表A,B,C,D或&,|。A,B,C,D的值是0或1。再給你m個(gè)條件$a,b,c,d,e$，代表A,B,C,D分別等于a,b,c,d時(shí)表達(dá)式的值為e。求有多少種將?填滿的方式，符合給出的所有條件？

$n\le 500,m\le 2^4$

題解：CF總考這種用二進(jìn)制表示特殊狀態(tài)的題，感覺十分考驗(yàn)人類的抽象能力。

因?yàn)樽兞康目赡芮闆r的只有$2^4$種，所以我們用一個(gè)4位的二進(jìn)制字符表示。這樣一來我們就可以發(fā)現(xiàn)可能的表達(dá)式只有$2^{2^4}$種，所以我們?cè)儆靡粋€(gè)16位的二進(jìn)制來表示一個(gè)表達(dá)式（不要暈）。這個(gè)二進(jìn)制數(shù)的第i位為0/1的意義是：如果把i用二進(jìn)制表示，則i的每一位代表每個(gè)變量的取值。在這些變量分別取這些值時(shí)，這個(gè)表達(dá)式的值為0/1（千萬不要暈）。

因?yàn)楸磉_(dá)式是一堆括號(hào)圍出來的，我們可以將括號(hào)的嵌套看成一個(gè)樹形結(jié)構(gòu)，并且是一棵二叉樹。我們?cè)O(shè)f[x][S]表示對(duì)于當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的子樹，有多少種方法使得得到的表達(dá)式為S。轉(zhuǎn)移時(shí)我們通過左右兒子的f以及當(dāng)前節(jié)點(diǎn)的運(yùn)算符即能確定當(dāng)前節(jié)點(diǎn)的f值。然后你會(huì)發(fā)現(xiàn)轉(zhuǎn)移的實(shí)質(zhì)就是FWT。。。

#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; const int P=1000000007; char str[510]; int n,m,tot; int f[170][(1<<16)+4],g[(1<<16)+4],p1[20],p2[20]; inline void add(int &x,int y) {x+=y; if(x>=P) x-=P;} inline void dec(int &x,int y) {x-=y; if(x<=0) x+=P;} inline void fwt1(int *a) {for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if((i>>h)&1) add(a[i],a[i^(1<<h)]); } inline void ufwt1(int *a) {for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if((i>>h)&1) dec(a[i],a[i^(1<<h)]); } inline void fwt0(int *a) {for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if(!((i>>h)&1)) add(a[i],a[i|(1<<h)]); } inline void ufwt0(int *a) {for(int h=0;h<16;h++) for(int i=0;i<(1<<16);i++) if(!((i>>h)&1)) dec(a[i],a[i|(1<<h)]); } int build(int l,int r) {int x=++tot;if(l==r){int i,j,S;for(j=0;j<4;j++){if(str[l]=='?'||str[l]=='A'+j){for(S=i=0;i<16;i++) if((i>>j)&1) S|=1<<i;f[x][S]++;}if(str[l]=='?'||str[l]=='a'+j){for(S=i=0;i<16;i++) if(!((i>>j)&1)) S|=1<<i;f[x][S]++;}}return x;}int i,mid,t=0;for(i=l;i<=r;i++){t+=(str[i]=='(')-(str[i]==')');if(!t) break;}mid=i+1;int ls=build(l+1,mid-2),rs=build(mid+2,r-1);if(str[mid]=='|'){fwt1(f[ls]),fwt1(f[rs]);for(i=0;i<(1<<16);i++) f[x][i]=1ll*f[ls][i]*f[rs][i]%P;ufwt1(f[x]);}else if(str[mid]=='&'){fwt0(f[ls]),fwt0(f[rs]);for(i=0;i<(1<<16);i++) f[x][i]=1ll*f[ls][i]*f[rs][i]%P;ufwt0(f[x]);}else{fwt0(f[ls]),fwt0(f[rs]);for(i=0;i<(1<<16);i++) g[i]=1ll*f[ls][i]*f[rs][i]%P;ufwt0(g),ufwt0(f[ls]),ufwt0(f[rs]);memcpy(f[x],g,sizeof(g));fwt1(f[ls]),fwt1(f[rs]);for(i=0;i<(1<<16);i++) g[i]=1ll*f[ls][i]*f[rs][i]%P;ufwt1(g);for(i=0;i<(1<<16);i++) add(f[x][i],g[i]);}return x; } int main() {scanf("%s%d",str+1,&m),n=strlen(str+1);int i,j,ans=0,S=0,t;for(i=1;i<=m;i++){for(S=j=0;j<4;j++) scanf("%d",&t),S|=t<<j;scanf("%d",&t),p1[i]=S,p2[i]=t;}build(1,n);for(i=0;i<(1<<16);i++){for(j=1;j<=m;j++) if(((i>>p1[j])&1)!=p2[j]) break;if(j>m) add(ans,f[1][i]);}printf("%d",ans);return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的【CF582E】Boolean Function 树形DP+FWT的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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