题目链接
题目思路
这个不知道叫啥感觉算是个二进制dp把
设\(n\)为化简为\(2\)进制的最高位数
我最开始是直接\(3^n\)枚举子集，但是喜提\(TLE\)
标准是\(n\times2^n\)
每次枚举只枚举比他多一个1的元素，然后从大到小for过去就能得到答案
因为比他多一个1的元素也枚举了比他多一个1的元素，递归的思路，这样其实相当于枚举了他的所有父亲
注意有负数
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=6e5+5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n;
ll dp1[maxn][2],dp2[maxn][2];
ll ans[maxn];
int main(){
int _; scanf("%d",&_);
while(_--){
scanf("%d",&n);
for(int i=0,a;i<=n-1;i++){
scanf("%d",&a);
dp1[i][0]=dp1[i][1]=a;
}
for(int i=0,b;i<=n-1;i++){
scanf("%d",&b);
dp2[i][0]=dp2[i][1]=b;
}
int m=1;
while(m<n-1) m=(m<<1);
for(int i=0;i<=19;i++){
for(int j=m-1;j>=0;j--){
if((!(j&(1<<i)))&&j<=n-1&&(j^(1<<i))<=n-1){
dp1[j][0]=min(dp1[j^(1<<i)][0],dp1[j][0]);
dp1[j][1]=max(dp1[j^(1<<i)][1],dp1[j][1]);
dp2[j][0]=min(dp2[j^(1<<i)][0],dp2[j][0]);
dp2[j][1]=max(dp2[j^(1<<i)][1],dp2[j][1]);
}
}
}
ans[n]=-INF;
ll pr=0;
for(int i=n-1;i>=0;i--){
ans[i]=max(max(dp1[i][0]*dp2[i][0],dp1[i][0]*dp2[i][1]),max(dp1[i][1]*dp2[i][0],dp1[i][1]*dp2[i][1]));
ans[i]=max(ans[i],ans[i+1]);
pr=(pr+ans[i])%mod;
}
printf("%lld\n",(pr%mod+mod)%mod);
}
return 0;
}