牛客网暑期ACM多校训练营（第七场）Bit Compression

链接：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- and s2i. For example, if we apply XOR to {} we get {}.

After n operations, the string will have length .

There are 3n ways to choose the n operations in total. How many of these ways will give  as the only character of the final string.

输入描述:

The first line of input contains a single integer n ( ≤ n ≤ ).

The next line of input contains a single binary string s (|s| = 2n). All characters of s are either  or .

输出描述:

Output a single integer, the answer to the problem.

示例1

输入

复制

输出

复制

说明

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=<<;

int num[][maxn];

int vis[][maxn];

int val[][maxn];

int solve(int x)

{

 if(x==)

 return num[x][];

 int tmp=;

  if(x<=)

  {

      for(int i=;i<=<<x;i++)

      {

          tmp=(tmp<<)+num[x][i];

      }

      if(vis[x][tmp])

          return val[x][tmp];

  }

    int ans=;

    for(int i=,j=;i<=<<x;i+=){

        num[x-][++j]=num[x][i]^num[x][i+];

    }

    ans+=solve(x-);

    for(int i=,j=;i<=<<x;i+=){

        num[x-][++j]=num[x][i]&num[x][i+];

    }

    ans+=solve(x-);

    for(int i=,j=;i<=<<x;i+=){

        num[x-][++j]=num[x][i]|num[x][i+];

    }

    ans+=solve(x-);

    if(x<=){

        val[x][tmp]=ans;

        vis[x][tmp]=;

    }

    return ans;

}

int main()

{

    int n;

    string s;

    cin>>n>>s;

    for(int i=;i<<<n;i++)

    {

        num[n][i+]=s[i]-'';

    }

    printf("%d\n",solve(n));

    return ;

}