题目链接：Problem - 6971 (dingbacode.com)
?题意：有两个长度为n的序列A和序列B，定义一个长度为n的序列C，其中
? ? ? ? ? ? Ck=max{Ai，Bj}（i&j>=k）算出C0+C1+...Cn-1的值
题解：
i&j>=k,min(i,j)>=k,所以i
A[i]表示二进制i为1的位置一定为1，i为0的位置可能为1可能为0? A数组中数的最大值
a[i]表示二进制i为1的位置一定为1，i为0的位置可能为1可能为0? A数组中数的最小值
B[i],b[i]同理
例如：n=8，n-1=7为111
A[111]=max(A[111])，B也同理
A[110]=max(A[110],A[111])
A[101]=max(A[101],A[111])
A[100]=max(A[100],A[101],A[110])? ?因为111的情况已经包含在其中的数组中
A[011]=max(A[011],A[111])
A[010]=max(A[010],A[011],A[110])
A[001]=max(A[001],A[011],A[101])
A[000]=max(A[001],A[010],A[100])
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const ll inf = 1000000007;//1e9+7
const int N = 20000010;
const int mod = 998244353;
ll n, A[N], B[N], a[N], b[N];
ll ans[N];
int main()
{
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++)
{
scanf("%lld", &A[i]);
a[i] = A[i];
}
for (int i = 0; i < n; i++)
{
scanf("%lld", &B[i]);
b[i] = B[i];
}
int m = 1;
while (m < n) m = m << 1;//求出和n同位数中的最大值，例如n为110，那么m为111
for (int i = n; i <= m; i++)
{
A[i] = B[i] = -inf;//求最大值，所以先给赋一个极小值
a[i] = b[i] = inf;//求最小值，所以先给赋一个极大值
}
//从最后一位开始考虑
for (int i = n - 1; i >= 0; i--)
{
for (int j = 1; j < m; j <<= 1)//往左移右边补0
{
if (!(i & j))//i的第j位有0
{
A[i] = max(A[i], A[i ^ j]);//1^1=0 0^1=1
B[i] = max(B[i], B[i ^ j]);
a[i] = min(a[i], a[i ^ j]);
b[i] = min(b[i], b[i ^ j]);
}
}
}
ans[n] = -(ll)inf * inf;//可能超过1e18
for (int i = n - 1; i >= 0; i--)
{
ans[i] = -(ll)inf * inf;
ans[i] = max(ans[i], (ll)A[i] * B[i]);//都为正数
ans[i] = max(ans[i], (ll)A[i] * b[i]);//一正一负
ans[i] = max(ans[i], (ll)a[i] * B[i]);//一负一正
ans[i] = max(ans[i], (ll)a[i] * b[i]);//都为负数
ans[i] = max(ans[i], ans[i + 1]);
}
ll res = 0;
for (int i = 0; i < n; i++)
{
res = (res + ans[i]) % mod;
}
res = (res + mod) % mod; //ans[i]可能是负的
cout << res << endl;
}
return 0;
}