牛客多校 Bit Compression (暴力)

给出一个2^18位的01串,每次可以把他折半,两位两位之间进行 &|^ 三种操作,
问你有多少种方法可以使得最后变成一个1(18次操作).
暴力即可.可以先做一些预处理.

#include <iostream>
#include <vector>
#include <cstring>
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 17;
const int MOD = 998244353;
char a[18+3][MAXN],sv[MAXN];
LL rem[MAXN];
LL n,ans;
int pre(int p)
{
    LL ret = 0;
    if(p==n)
    {
        if(a[p][0]=='1') ret++;
        return ret;
    }
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')&(a[p][2*i+1]-'0'))+'0';
    ret += pre(p+1);
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')|(a[p][2*i+1]-'0'))+'0';
    ret += pre(p+1);
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')^(a[p][2*i+1]-'0'))+'0';
    ret += pre(p+1);
    return ret;
}
void dfs(int p)
{
    if(p==n-4)
    {
        int tmp = 0;
        for (int i = 0; i < 32; ++i)
            tmp += (a[p][i]-'0')<<(31-i);
        ans += rem[tmp];
        return ;
    }
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')&(a[p][2*i+1]-'0'))+'0';
    dfs(p+1);
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')|(a[p][2*i+1]-'0'))+'0';
    dfs(p+1);
    for (int i = 0; i < 1<<(n-p-1); ++i)
        a[p+1][i] = ((a[p][2*i]-'0')^(a[p][2*i+1]-'0'))+'0';
    dfs(p+1);
}
int main()
{
#ifdef noob
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
#endif
    cin>>n;
    ans = 0;
    scanf("%s",a[0]);
    if(n<=5)
        cout<<pre(0)<<endl;
    else
    {
        int sn = n;
        memcpy(sv,a[0],1<<n);
        n = 5;
        for(int i=0;i<1<<32;++i)
        {
            for(int j=0;j<32;++j)
            {
                if((i>>j)&1)
                    a[0][31-j] = '1';
                else
                    a[0][31-j] = '0';
            }
            rem[i] = pre(0);
        }
        n = sn;
        memcpy(a[0],sv,1<<n);
        dfs(0);
        cout<<ans<<endl;
    }
    return 0;
}

这题当时没有做出来,因为忽略了这题最暴力也只是在不到1e8的范围,所以希望存在某种算法,当然是没有的.只要做一些小优化就好.
有的大佬直接用大量stl都爆过去,真是太丢人了.
这里就是做一些预处理,其实不必要.
不能再走这种弯路了.