链接：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<=4打印出来。这样就跑到4就结束了。不能只开一个数组，因为等于0不代表没跑到过。比如0000.跑到了ans还是0
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int maxn=1<<17;
int num[20][maxn];
int vis[20][maxn];
int val[20][maxn];
int solve(int x)
{
if(x==0)
return num[x][1];
int tmp=0;
if(x<=4)
{
for(int i=1;i<=1<<x;i++)
{
tmp=(tmp<<1)+num[x][i];
}
if(vis[x][tmp])
return val[x][tmp];
}
int ans=0;
for(int i=1,j=0;i<=1<<x;i+=2){
num[x-1][++j]=num[x][i]^num[x][i+1];
}
ans+=solve(x-1);
for(int i=1,j=0;i<=1<<x;i+=2){
num[x-1][++j]=num[x][i]&num[x][i+1];
}
ans+=solve(x-1);
for(int i=1,j=0;i<=1<<x;i+=2){
num[x-1][++j]=num[x][i]|num[x][i+1];
}
ans+=solve(x-1);
if(x<=4){
val[x][tmp]=ans;
vis[x][tmp]=1;
}
return ans;
}
int main()
{
int n;
string s;
cin>>n>>s;
for(int i=0;i<1<<n;i++)
{
num[n][i+1]=s[i]-'0';
}
printf("%d
",solve(n));
return 0;
}