链接：https://www.nowcoder.com/acm/contest/145/C

来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

Special Judge, 64bit IO Format: %lld

题目描述

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.

发现读题的时候理解有点偏差

每次操作应该是固定的 也就是说从头到尾做一次操作 这个位运算符都是一样的

暴力也不会.....用map优化的暴力

mp[i]表示关键字的字符串长度都是2^i

哦值得一提 牛客网c++11TLE c++14能过

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stack>

#include<queue>

#include<map>

#define inf 0x3f3f3f3f

using namespace std;

int n;

const int maxn = 20;

string s;

map<string, int> mp[maxn];

int main()

{

	while(scanf("%d", &n) != EOF){

        cin>>s;

        mp[n][s] = 1;

        for(int i = n; i >= 1; i--){

            map<string, int>::iterator it;

            for(it = mp[i].begin(); it != mp[i].end(); it++){

                s = it->first;

                int cnt = it->second;

                int len = 1 << i;

                string sa = "", sb = "", sc = "";

                for(int j = 0; j < len; j += 2){

                    sa += ((s[j] - '0') & (s[j + 1] - '0')) + '0';

                    sb += ((s[j] - '0') | (s[j + 1] - '0')) + '0';

                    sc += ((s[j] - '0') ^ (s[j + 1] - '0')) + '0';

                }

                mp[i - 1][sa] += cnt;

                mp[i - 1][sb] += cnt;

                mp[i - 1][sc] += cnt;

            }

        }

        printf("%d\n", mp[0]["1"]);

	}

	return 0;

}