Bit Compression

链接：https://www.nowcoder.com/acm/contest/145/C
来源：牛客网
 

题目描述

A binary string s of length N = 2n is given. You will perform the following operation n times :

- Choose one of the operators AND (&), OR (|) or XOR (^). Suppose the current string is S = s1s2...sk. Then, for all , replace s2i-1s2i with the result obtained by applying the operator to s2i-1 and s2i. For example, if we apply XOR to {1101} we get {01}.

After n operations, the string will have length 1.

There are 3n ways to choose the n operations in total. How many of these ways will give 1 as the only character of the final string.

输入描述:

The first line of input contains a single integer n (1 ≤ n ≤ 18).

The next line of input contains a single binary string s (|s| = 2n). All characters of s are either 0 or 1.

输出描述:

Output a single integer, the answer to the problem.

 

示例1

输入

复制

2
1001

输出

复制

4

说明

The sequences (XOR, OR), (XOR, AND), (OR, OR), (OR, AND) works.

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)


map<string,int> str_cnt;

int flag=0;

int dfs(string str,int len){

   // cout<<str<<endl;
    if(flag&&len==16)  return str_cnt[str];
    if(len==1 )  return str[0]=='1';

    int ans=0;
    string s1="",s2="",s3="";
    int cnt=0;
    int f1=0,f2=0,f3=0;
    for(int i=0;i<len;i+=2){
        s1+= ((str[i]-'0')&(str[i+1]-'0'))+'0';
        s2+= ((str[i]-'0')|(str[i+1]-'0'))+'0';
        s3+= ((str[i]-'0')^(str[i+1]-'0'))+'0';
        if(s1[cnt]!='0')f1=1;
        if(s2[cnt]!='0')f2=1;
        if(s3[cnt]!='0')f3=1;
        cnt++;
    }
    if(f1) ans+=dfs(s1,len/2);
    if(f2) ans+=dfs(s2,len/2);
    if(f3) ans+=dfs(s3,len/2);
    return ans;
}

void create(string s,int len){
    if(len==16){
        str_cnt[s]=dfs(s,16);
        //cout<<s<<" "<<str_cnt[s]<<endl;
        return;
    }
    s+='0';
    create(s,len+1);
    s[len]='1';
    create(s,len+1);
}

void init(){
    string s="";
    create(s,0);
}
/*
优化常数：平常就得注意

学习的点：
1.要学会剪枝
2.要学会预处理(也就是重复的部分，不要让他一直在查询) 
先预处理出来，这样就把最多的叶子节点少了好多
*/

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    init();
    flag=1;
    int n;
    cin>>n;
    string str;
    cin>>str;

    int ans=dfs(str,(1<<n));
    cout<<ans<<'\n';
    return 0;
}

转载 

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)


map<string,int> str_cnt[20];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    string str,s1,s2,s3;
    cin>>str;
    str_cnt[n][str]=1;
    map<string,int>::iterator it;
    for(int i=n-1;i>=0;i--){
        int len=1<<i;
        for(it=str_cnt[i+1].begin();it!=str_cnt[i+1].end();it++){
            str=it->first;
            int num=it->second;
            s1=s2=s3="";
            for(int j=0;j<len;j++){
                s1+=((str[j<<1]-'0')&(str[j<<1|1]-'0'))+'0';
                s2+=((str[j<<1]-'0')|(str[j<<1|1]-'0'))+'0';
                s3+=((str[j<<1]-'0')^(str[j<<1|1]-'0'))+'0';
            }
            str_cnt[i][s1]+=num;
            str_cnt[i][s2]+=num;
            str_cnt[i][s3]+=num;
        }
    }
    cout<<str_cnt[0]["1"]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)


const int maxn=1e6+10;
char str[maxn];

int tr[maxn<<1];

int ans=0;
/*
这个存储结构我只能说太牛逼了，真的太秀了

只需要开一个数组，充分利用了2^n

*/
void dfs(int n){
    if(n==-1){
        ans+=(tr[1]==1);
        return;
    }
    int len=1<<n;int f1=0,f2=0,f3=0;
    rep(i,0,len){
        tr[len+i]=tr[(len+i)<<1]&tr[(len+i)<<1|1];if(tr[len+i])f1=1;
    }
    if(f1) dfs(n-1);
    rep(i,0,len){
        tr[len+i]=tr[(len+i)<<1]|tr[(len+i)<<1|1];if(tr[len+i])f2=1;
    }
    if(f2) dfs(n-1);
    rep(i,0,len){
        tr[len+i]=tr[(len+i)<<1]^tr[(len+i)<<1|1];if(tr[len+i])f3=1;
    }
    if(f3) dfs(n-1);
}

int main(){
    int n;
    scanf("%d",&n);
    scanf("%s",str);
    int len=1<<n;
    rep(i,0,len)tr[len+i]=str[i]-'0';
    dfs(n-1);
    printf("%d\n",ans);
    return 0;
}