牛客多校训练----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.

 

一个长度为n的01字符串，第i个和第i+1个经过^或者|或者&运算后合并，问最终01串变成1的方法有多少种。

直接暴力。

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

map<string,int>mp[21];
map<string,int>::iterator it;

int main()
{
    int n,len,i,j;
    string s,t;
    cin>>n>>s;
    mp[0][s]=1;
    for(i=1;i<=n;i++)
    {
         for(it=mp[i-1].begin();it!=mp[i-1].end();it++)
         {
             s=it->first;
             len=s.length();
             t="";
             for(j=0;j<len;j+=2)
                 t+=((s[j]-'0')|(s[j+1]-'0'))+'0';
             mp[i][t]+=it->second;
             t="";
             for(j=0;j<len;j+=2)
                 t+=((s[j]-'0')&(s[j+1]-'0'))+'0';
             mp[i][t]+=it->second;
             t="";
             for(j=0;j<len;j+=2)
                 t+=((s[j]-'0')^(s[j+1]-'0'))+'0';
             mp[i][t]+=it->second;
         }
    }
    printf("%d\n",mp[n]["1"]);
    return 0;
}