链接：https://www.nowcoder.com/acm/contest/145/C
来源：牛客网
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| = 2
n
). All characters of s are either 0 or 1.
Output a single integer, the answer to the problem.
The sequences (XOR, OR), (XOR, AND), (OR, OR), (OR, AND) works.
题意：给你2^n个数，每次可以将前2^(n-1)个数和后2^(n-1)个数进行二进制与、或、异或操作中的一种，问有多少种不同的操作顺序使得最后的结果为一个一？
分析：考虑直接暴力的时间复杂度是3^18，这个数与题目给出的时间限制已经很接近，所以我们只需要在直接暴力的基础上做一点点优化就可以了
考虑如果最后要得到一个一，则数列中一定要还存在一，否则无论与、或、异或操作都无法再得到一
所以我们只需要在暴力的时候判断下剩下的数中是否还有一，没有一就没必要继续操作
AC代码：
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 10;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
const double pi = acos(-1.0);
string s;
ll t[maxn*2]; //开始将数字存在1<<n后，每次数字合并后产生的1<<(n-1)往前面放，方便合并运算
ll res = 0;
void dfs( ll n ) {
if( n == -1 ) {
if( t[2] == 1 ) { //只剩一个一
res ++;
}
return ;
}
ll k = 1<<n;
for( ll j = 0; j <= 2; j ++ ) {
ll cnt = 0;
for( ll i = 1; i <= k; i ++ ) {
ll tmp = i+k;
if( j == 0 ) {
t[tmp] = t[tmp*2-1]^t[tmp*2];
} else if( j == 1 ) {
t[tmp] = t[tmp*2-1]|t[tmp*2];
} else {
t[tmp] = t[tmp*2-1]&t[tmp*2];
}
if( t[tmp] == 0 ) {
cnt ++;
}
}
if( cnt == k ) { //如果都是零就不可能再出现一
continue;
}
dfs(n-1);
}
}
int main() {
ll n;
cin >> n;
cin >> s;
ll k = 1<<n;
for( ll i = 1; i <= k; i ++ ) {
t[i+k] = s[i-1] - ‘0‘;
}
dfs(n-1);
cout << res << endl;
return 0;
}
原文：https://www.cnblogs.com/l609929321/p/9550895.html