C++14(g++5.4) 解法, 执行用时: 1248ms, 内存消耗: 1248K, 提交时间: 2020-04-05 17:25:56

#include<cstdio>
using namespace std;
bool a[1 << 18];
int dfs(int n, bool* s) {
	if (n == 1) return 1;
	n >>= 1; bool b[n]; int ans = 0, h1 = 0, h2 = 0, h3 = 0;
	for(int i=0;i<n;++i)h1+=b[i]=(s[i<<1]&s[i<<1|1]); if(h1)ans+=dfs(n,b);
	for(int i=0;i<n;++i)h2+=b[i]=(s[i<<1]|s[i<<1|1]); if(h2)ans+=dfs(n,b);
	for(int i=0;i<n;++i)h3+=b[i]=(s[i<<1]^s[i<<1|1]); if(h3)ans+=dfs(n,b);
	return ans;
}
int main() {
	int n; scanf("%d%", &n);
	for(int i=0;i<(1<<n);++i) scanf("%1d",&a[i]);
	printf("%d\n", dfs(1 << n, a));
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1516ms, 内存消耗: 2912K, 提交时间: 2018-08-09 20:27:24

#include<cstdio>
#define R(i,a) for(int i=0;i<(1<<a);i++)
int N[20][300030],A=0,x,y;char s[300030];
int C(int o,int a,int b){if(o==0)return a^b;return(o==1)?a&b:a|b;}
void D(int c){
	y=0;R(i,c)y+=N[c+1][i];
	if(!y)return;if(!c){A++;return;}
	for(int o=0;o<3;o++){R(i,c-1)N[c][i]=C(o,N[c+1][i<<1],N[c+1][i<<1|1]);D(c-1);}
}
int main(){
	scanf("%d%s",&x,s);
	R(i,x)N[x+1][i]=s[i]-'0';
	D(x);printf("%d\n",A);
	return 0;
}