Bit Compressionの2つのソリューションO(∩∩)Oははは~

タイトルリンク
方法一(暴力):この問題は典型的なdfs問題であることがわかりやすく、枝切り(結果を必ず0にする場合に枝切りを行う)に注意すれば通過できます.以下はコードです.

#include
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%*c", &n);
	for(int i=0;i<(1<<n);++i) a[i]=getchar()-'0';
	printf("%d
", dfs(1 << n, a));
	return 0;
}

方法二(非暴力):dfsを記憶最適化し,数ビットdpでバイナリ逆転ソートを求め,高精度圧位でデータオーバーフロー防止などを行った.(暴力法よりずっと速い)コードは以下の通りです.

#include

using namespace std;

const int  N  = 1 << 18;

int a[N], pos[N], b[N];// a     ，pos    ，b      
unsigned c[N], d[N];// c       ，d         

void Bitsort(int n) { //   dp 
	for(int i = 0; i <= (1 << n); ++i) {
		pos[i] = pos[i>>1]>>1|(i&1)<<(n-1);
	} 
}

int pre(int n, int last) { //      
	if (n == 1) return last&1;
	n >>= 1;
	int x = last, y = last >> n;
	return pre(n,x&y)+pre(n,x|y)+pre(n,x^y);
}

int dfs(int n, unsigned* last, unsigned* next) { // dfs
	if (n == 1 ) return last[0] & 1;
	if (n == 16) return b[last[0] & 0xffff];
	int ans = 0;
	if (n > 32){
		int temp = n / 64;
		for(int i = 0; i < temp; ++i) next[i] = last[i] & last[i+temp];
		ans += dfs(n / 2, next, next + temp);
		for(int i = 0; i < temp; ++i) next[i] = last[i] | last[i+temp];
		ans += dfs(n / 2, next, next + temp);
		for(int i = 0; i < temp; ++i) next[i] = last[i] ^ last[i+temp];
		ans += dfs(n / 2, next, next + temp); 
	}
	else {
		int x = last[0];
		int y = last[0] >> n / 2;
		next[0] = x & y;
		ans += dfs(n / 2, next, next + 1);
		next[0] = x | y;
		ans += dfs(n / 2, next, next + 1);
		next[0] = x ^ y;
		ans += dfs(n / 2, next, next + 1);
	}
	return ans;
} 

int main() {
	int n;
	scanf("%d%*c", &n);
	/******************************** 
	        
	           
 	     (    32  ->    ) 
 	       n=4,      
	***********************************/
	Bitsort(n);
	for(int i=0;i<1<<n;++i) a[pos[i]]=getchar()-'0';
	for(int i=0;i<1<<n;++i) c[i/32]|=(unsigned)a[i]<<(i%32);
	for(int i=0;i<1<<16;++i) b[i]=pre(16,i);
	printf("%d
", dfs(1 << n, c, d)); 
	return 0; 
}