AT_abc291_g [ABC291G] OR Sum 题解

· · 题解

AT_abc291_g [ABC291G] OR Sum 题解

一看到字符串匹配问题，就不由得想到了 FFT。

题目要求的其实是这个东西：

\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}A_i|B_{i-k}

由于多位的按位或不能变为加减乘除的形式，所以考虑拆位；又因为 A_i，B_i 均小于等于 31，所以最多有 5 位，再加上 8s 的时间与 1GB 的内存，所以这样能过。

拆位，得：

\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}\sum^4_{j=0}A_{i,\,j}|B_{i-k,\,j}

又因为 x|y=x+y-xy=x(1-y)+y，所以原式可化简为：

\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}\sum^4_{j=0}A_{i,\,j}(1-B_{i-k,j})+B_{i-k,\,j}

令 B^{'}_{i,\,j}=1-B_{i,\,j}，则原式可化简为：

\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}\sum^4_{j=0}A_{i,\,j}B^{'}_{i-k,\,j}+B_{i-k,\,j}

我们发现：

\sum^{n+k-1}_{i=k}\sum^4_{j=0}B_{i-k,\,j}

是定值，值为 B 中所有元素二进制中 1 的位数之和，令其为 sum，则原式可化简为：

\large sum+\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}\sum^4_{j=0}A_{i,\,j}B^{'}_{i-k,\,j}

又因为多项式乘法中，h_i 的系数为 ：\sum^{i}_{j=1}f_j\text{ × }g_{i-j}，所以我们要让原式中的两个下标的和为定值，不难想到将 B^{'} 翻转一下。

令 B^{''}=B^{'}_{n-i-1,\,j}，则 B^{'}=B^{''}_{n-i-1,\,j}，所以原式可化简为：

\large sum+\large\max^{n-1}_{k=0}\sum^{n+k-1}_{i=k}\sum^4_{j=0}A_{i,\,j}B^{''}_{n-i+k-1,\,j}

此时，\text{max} 里的值就为 A\times B 的第 n+k-1 位，就可以用 FFT 切了。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1 << 22) + 10;//要开到这，不然可能会RE 
const double pi = acos(-1);//反三角函数 
struct z{
    double a,b;
    z operator + (z other)
    {
        return {this -> a + other.a,this -> b + other.b};
    }
    z operator - (z other)
    {
        return {this -> a - other.a,this -> b - other.b};
    }
    z operator * (z other)
    {
        return {this -> a * other.a - this -> b * other.b,this -> a * other.b + this -> b * other.a};
    }//重载运算符 
}A[maxn][5],B[maxn][5],B_[maxn][5],B__[maxn][5],H[maxn][5];//一个下划线代表一个'，例如B_就是前面推导过程中的B' 
int n,a[maxn],b[maxn],sum,ans,maxx = 0,len = 1;
void FFT(z f[maxn][5],int l,int op,int j)
{
    if(l == 1) return ;//判边界 
    z A0[l >> 1][5],A1[l >> 1][5];
    for(int i = 0;i < l;i++)//奇偶拆分 
    {
        if(i & 1) A1[i >> 1][j] = f[i][j];
        else A0[i >> 1][j] = f[i][j];
    }
    FFT(A0,l >> 1,op,j);
    FFT(A1,l >> 1,op,j);//递归 
    z w = {1,0},wk = {cos(2.0 * pi / l),op * sin(2.0 * pi / l)};//不要忘记乘op 
    for(int i = 0;i < (l >> 1);i++,w = w * wk)
    {
        f[i][j] = A0[i][j] + w * A1[i][j];
        f[i + (l >> 1)][j] = A0[i][j] - w * A1[i][j];//O1赋值另一半 
    }
    return ;
}
int main()
{
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    for(int i = n;i < 2 * n;i++)
    {
        a[i] = a[i - n];
    }
    for(int i = 0;i < 2 * n;i++)
    {
        A[i][0].a = a[i] % 2;
        a[i] >>= 1;
        A[i][1].a = a[i] % 2;
        a[i] >>= 1;
        A[i][2].a = a[i] % 2;
        a[i] >>= 1;
        A[i][3].a = a[i] % 2;
        a[i] >>= 1;
        A[i][4].a = a[i] % 2;
    }
    for(int i = 0;i < n;i++)
    {
        cin >> b[i];
        B[i][0].a = b[i] % 2;
        sum += B[i][0].a;
        b[i] >>= 1;
        B[i][1].a = b[i] % 2;
        sum += ((int)(B[i][1].a + 0.5) << 1);
        b[i] >>= 1;
        B[i][2].a = b[i] % 2;
        sum += ((int)(B[i][2].a + 0.5) << 2);
        b[i] >>= 1;
        B[i][3].a = b[i] % 2;
        sum += ((int)(B[i][3].a + 0.5) << 3);
        b[i] >>= 1;
        B[i][4].a = b[i] % 2;
        sum += ((int)(B[i][4].a + 0.5) << 4);
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            B_[i][j].a = 1 - B[i][j].a;
        }
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            B__[i][j].a = B_[n - i - 1][j].a;
        }
    }
    while(len <= 3 * n - 1) len <<= 1;
    //以上为初始化 
    for(int i = 0;i < 5;i++)
    {
        FFT(A,len,1,i);
        FFT(B__,len,1,i);//求单位根点值 
    }
    for(int i = 0;i < len;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            H[i][j] = A[i][j] * B__[i][j]; 
        }
    }
    for(int i = 0;i < 5;i++) FFT(H,len,-1,i);//逆运算 
    for(int i = 0;i < len;i++)
    {
        for(int j = 0;j < 5;j++)
        {
            H[i][j].a = ((int)(H[i][j].a / len + 0.5)) * (1 << j);//千万不要忘了乘(1 << j)，拆位之后还要合并 
        }
    }
    for(int k = 0;k < n;k++)
    {
        ans = 0;
        for(int j = 0;j < 5;j++)
        {
            ans += (H[n + k - 1][j].a + 0.5);
        }
        maxx = max(maxx,ans);//求值 
    }
    cout << maxx + sum << '\n';//又切一道紫 
    return 0;
}