[ABC291G] OR Sum 题解

题意：

给定两个长为 \(n\) 的序列 \(A_i,B_i\) 。

你可以对 \(A\) 进行若干次循环移位操作，即

对于任意 \(i~(0 \le i < n)\) ，令 \(A'_i \gets A_{(i + 1) \bmod n}\) 。

然后令 \(A \gets A'\) ，这相当于让 \(A\) 整体向左循环移位了一次。

请求出 \[ \max\left\{\sum_{i=0}^{n-1}\ (A_i \lor B_i)\right\} \] 其中 \(\lor\) 表示二进制下的或运算。

数据范围：

\(2 \le n \le 5\times10^5,~0 \le A_i,B_i \le 31\)

发现 \(\lor\) 操作并不好做，考虑将 \(A_i,B_i\) 取反，然后求 \(\land\) 的最小值。

枚举循环移位了 \(j\) 次，考察 \(A,B\) 二进制下第 \(k\) 位，记为 \(a,b\) 。

那么记答案为 \(c_j\) ，则有 \[ c_j = \sum_{i = 0}^{n-1} a_i\cdot b_{(i + j) \bmod n}\qquad(0 \le j \le n - 1) \] 提示：显然对 \(A\) 循环移位等价于对 \(B\) 反向循环移位

接下来就开始喵喵操作了：

把 \(b\) 复制一遍，得到 \(c_j = \sum a_i \cdot b_{i + j}\)
记 \(k = i+j\) ，得到 \(c_{k - i} = \sum a_i \cdot b_k\)
把 \(i\) 改成 \(-i\) ，得到 \(c_{k + i} = \sum a_{n-1 - i}\cdot b_k\)

现在令 \(a'\) 为 \(a\) 翻转后的结果，整理可得 \[ c_{i + j} = \sum_{i=0}^{n-1} a'_{i}\cdot b_j\qquad (n-1 \le j \le 2n - 2) \] 显然这是一个卷积，而答案的值域 \(V \le 1.6\times 10^7\) ，可以直接用 NTT 。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

namespace NTT
{
    #define NTT_N ((N + N) * 2)
    const int P = 998244353;
    const int G = 3, Gi = 332748118;
    int qpow(int a, int b)
    {
        int r = 1;
        for(a %= P; b; b >>= 1, a = 1ll * a * a % P)
            if(b & 1) r = 1ll * r * a % P;
        return r;
    }
    int l, limit, r[NTT_N], a[NTT_N], b[NTT_N];
    void init(int len) // size(a) plus size(b)
    {
        for(limit = 1, l = 0; limit <= len; limit *= 2, ++l);
        for(int i = 0; i < limit; i++)
            r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    }
    void NTT(int *A, int type)
    {
        for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
        for(int mid = 1; mid < limit; mid *= 2)
        {
            int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
            for(int j = 0; j < limit; j += (mid * 2))
            {
                int w = 1;
                for(int k = 0; k < mid; k++, w = 1ll * w * Wn % P)
                {
                    int x = A[j + k], y = 1ll * w * A[j + k + mid] % P;
                    A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
                }
            }
        }
        if(type != 1)
        {
            const int Inv = qpow(limit, P - 2);
            for(int i = 0; i < limit; i++) A[i] = 1ll * A[i] * Inv % P;
        }
    }
    int* convolution(int *A, int n, int *B, int m)
    {
        rep(i, 0, limit - 1) a[i] = b[i] = 0;
        rep(i, 0, n) a[i] = A[i]; rep(i, 0, m) b[i] = B[i];
        init(n + m + 1); NTT(a, 1); NTT(b, 1);
        for(int i = 0; i < limit; i++) a[i] = 1ll * a[i] * b[i] % P;
        NTT(a, -1); return a;
    }
}
int *t, a[N], b[N], c[N], d[N], f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, n - 1) cin >> b[i];
    rep(k, 0, 4)
    {
        rep(i, 0, n - 1)
        {
            c[n - i - 1] = ((~a[i]) >> k) & 1;
            d[i + n] = d[i] = ((~b[i]) >> k) & 1;
        }
        t = NTT::convolution(c, n - 1, d, n * 2 - 1);
        rep(i, 0, n - 1) f[i] += ((n - t[i + n - 1]) << k);
    }
    cout << *max_element(f, f + n) << '\n';
    return 0;
}