I love max and multiply

如果 ${a\&b>=k,b\&c>=k}$ ，那么 $a\&c>=k$ (具有传递性)

设 ${f[i]}$ 表示二进制数 ${j}$ 的集合，且满足 ${[j\&i>=k]}$ 。

如果我们从大到小计算 ${f[i]}$ ，那么 ${\sum_{[j=i\ XOR\ 2^{k},j!=i]}f[i]=f[i]\cup f[j]}$ 。因为 ${j>i}$ ，所以此时集合 ${f[j]}$ 已经得到了，并且可以保证的是所有满足 ${[x\&i>=k]}$ 的下标 ${x}$ 在上述的某个集合 ${f[j]}$ 中。

比如：n=32

${f[31]={11111}}$
${f[30]=\{11110\}\cup f[31]}$
${f[29]=\{11101\}\cup f[31]}$
${f[28]=\{11100\}\cup f[29]\cup f[30]}$
${f[27]=\{11011\}\cup f[31]}$
${f[26]=\{11010\}\cup f[27]\cup f[30]}$
${f[25]=\{11001\}\cup f[27]\cup f[29]}$

...

设 ${A[i]}$ 表示 ${max_{[j\&i>=k]}{a_j}}$ ， ${B[i]}$ 表示 ${max_{[j\&i>=k]}{b_j}}$ ， ${Aa[i]}$ 表示 ${min_{[j\&i>=k]}{a_j}}$ , ${Ba[i]}$ 表示 ${min_{[j\&i>=k]}{b_j}}$ 。那么我们可以在求出 ${f[j]}$ 的同时算出这些数组。

假设 $ans[i]$ 表示 ${max_{x,y\in f[i]}}a_x*a_y$ ，如果下标从大到小计算 ${C_i}$ ，那么 ${C_i=max(ans[i],C_{i+1})}$ 。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (2<<18)+7,mod=998244353;
const ll inf=1e18;
ll A[maxn],a[maxn],B[maxn],b[maxn];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T,n;
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=0;i<n;++i) cin>>a[i],A[i]=a[i];
        for(int i=0;i<n;++i) cin>>b[i],B[i]=b[i];
        int m=1;
        while(m<n) m<<=1;
        for(int i=n;i<m;++i) A[i]=B[i]=-inf,a[i]=b[i]=inf;
        for(int j=1;j<m;j<<=1)
        for(int i=m-1;~i;--i) if(!(i&j)){
            A[i]=max(A[i],A[i^j]);
            B[i]=max(B[i],B[i^j]);
            a[i]=min(a[i],a[i^j]);
            b[i]=min(b[i],b[i^j]);
        }
        ll ans(0),last=-inf,tmp;
        for(int i=n-1;~i;--i) {
            tmp=-inf;
            if(A[i]!=-inf&&B[i]!=-inf) tmp=max(tmp,A[i]*B[i]);
            if(A[i]!=-inf&&b[i]!=-inf) tmp=max(tmp,A[i]*b[i]);
            if(a[i]!=-inf&&B[i]!=-inf) tmp=max(tmp,a[i]*B[i]);
            if(a[i]!=-inf&&b[i]!=-inf) tmp=max(tmp,a[i]*b[i]);
            last=max(tmp,last);
            ans=(ans+last)%mod;
        }
        cout<<(ans+mod)%mod<<'\n';
    }
    return 0;
}