HDU6971 I love max and multiply（结论，推导）

题目：Problem - 6971 (dingbacode.com)

题目大意是给出an,bn数组，求一个c数组，其中Ck=max(ai*bj),i&j>=k，最后计算数组的和。首先注意到k可以向前覆盖（规定下标小的在前，大的在后），所以可以先求出i&j==k的情况下的c数组，然后再把大数向前覆盖小数，即从后向前保留最大数。

现在考虑Ck单点的情况，如果Ck是由ai*bj得到，那么i,j的二进制中都要“至少包含”k的二进制，即k的二进制中为1的位，那么i,j的二进制中对应位也是1，对于其他的位数，如果i,j对应位不相等则没有影响（与运算不等必为0），如果相等，此时i&j的值 kk>k,但答案是可以向前覆盖的，所以此时的答案对于Ck依然有效。

如果i,j二进制中不包含k的二进制，但是Ck这点确实是由i,j得到的，那么这种情况只能是i&j=kk>k,然后kk向前覆盖到k了。此时的i,j必然可以由更大的数，即kk枚举到，因为i,j的二进制中都必然包含kk的二进制(与运算性质）。

知道了每一位k所对应的i,j性质后，就可以枚举i,j了。这里的i，j只是代表a,b不同数组的下标，因为i,j的要求是相同的，只要满足即可，所以同时处理。但是该如何枚举又是个奇怪的问题。注意到n二进制最多18位，假设k有两位是1，那么要枚举剩下的16位一共2^16，k从1到n都算一遍，属实是多。

这时我们应该回想到本题最基本的性质，即答案可以向前覆盖。首先想到k从大到小处理，k越大，越不容易被覆盖，独立情况越多。然后枚举i,j，对于每个k,只枚举i,j比k最多多出一位1 的情况，如果i,j多出x位1，那么这种情况会在K时枚举到，这里K比k多出（x-1)位1。如果i,j多出不同数量的1也无所谓，因为我们的操作是记录，保留结果，假如i多出x位，j多出y位,那他们分别会在K比k多(x-1)位，K比k多（y-1)位时被枚举到，不用同时被枚举。

最后考虑结果，题目要求a*b尽可能大，所以保留枚举情况中最大数，又因为有负数，所以再保留一个最小数。每次算ck时，从amax，bmax,amin,bmin四个数中算乘积最大，同时向前覆盖，最后求和。

注意最后结果取模，可能是负数，要模成正的。

代码：

#include
using namespace std;
typedef long long int ll;
ll amx[262145], bmx[262145], amn[262145], bmn[262145];
ll mx[262145];
ll mo = 998244353;
int main()
{
int t, n;
ll x,ans;
int i,k;
cin >> t;
while (t--)
{
scanf("%d", &n);
for (i = 0;i <n;i++)scanf("%lld", &x), amx[i] = amn[i] = x;
for (i = 0;i <n;i++)scanf("%lld", &x), bmx[i] = bmn[i] = x;
for (k = n - 1;k >= 0;k--)
{
for (i = 0;(1 << i) <= n - 1;i++)
{
x = k | (1 << i);
if (x >= n)continue;
amx[k] = max(amx[k], amx[x]);
amn[k] = min(amn[k], amn[x]);
bmx[k] = max(bmx[k], bmx[x]);
bmn[k] = min(bmn[k], bmn[x]);
}
}
x = -(1ll << 62);
ans = 0;
for (i = n - 1;i >= 0;i--)
{
x = max(x, max(amx[i] * bmx[i], max(amn[i] * bmn[i], max(amx[i] * bmn[i], amn[i] * bmx[i]))));
ans += x;ans %= mo;
}
printf("%lld\n", (ans+mo)%mo);
}
}