SError_ Orz
[ABC291G] OR Sum
给定两个长为 \(n\) 的序列 \(A_i\)、\(B_i\)，循环移位 \(A_i\) 使得 $ \displaystyle\sum_{i=0}^{N-1}\ (A_i|B_i) $ 最大。
\(2 \le n \le 5\times10^5\)
\(0 \le A_i,B_i \le 31\)
拆位
\(31 = (11111)_2\)
怎么表述出原题的这个东西呢
暴力推下式子试试？
\[\begin {aligned} \sum _{i = 0} ^ {N - 1} (A_i | B_i) &= \sum _{i = 0} ^{N - 1} \sum _{j = 0} ^5 ([a_{ij} = 1] \or [b_{ij} = 1]) \times 2^j \\ &= \sum _{i = 0} ^{N - 1} \sum _{j = 0} ^5 (([a_{ij} = 1] + [b_{ij} = 1]) - [a_{ij} = 1][b_{ij} = 1]) \times 2^j \\ &= \sum _{i = 0} ^{N - 1} \sum _{j = 0} ^5 ((a_{ij} + b_{ij}) - a_{ij}b_{ij}) \times 2^j \\ &= \sum _{j = 0} ^5 2 ^ j \sum _{i = 0} ^ {N - 1}(a_{ij} + b_{ij} - a_{ij}b_{ij}) \\ &= \sum _{j = 0} ^5 2 ^ j \left( \sum_{i = 0} ^ {N - 1} a_{ij} + \sum _{i = 0} ^{N - 1} b_{ij} - \sum _{i = 0} ^ {N - 1} a_{ij}b_{ij} \right) \\ &= \sum _{j = 0} ^5 2 ^ j \left( \sum_{i = 0} ^ {N - 1} a_{ij} + \sum _{i = 0} ^{N - 1} b_{ij} \right) - \sum _{j = 0} ^5 2 ^ j\sum _{i = 0} ^ {N - 1} a_{ij}b_{ij} \end {aligned} \]无论怎么循环移位，前面的东西是不会变的，设前面为 \(res_1\)，那么现在目标就是最小化循环移位后后面的式子。考虑算出循环移位后的值。设循环移位 \(k\) 位的值是 \(c_k\)。
\[c_k = \sum _{j = 0} ^5 2 ^ j\sum _{i = 0} ^ {N - 1} a_{ij}b_{((i + k) \bmod n) j} \]后面的式子还是比较典的（指在 SError_ 指导前完全不会（Sto SError_ Orz
具体地：首先后面的式子与 \(j\) 无关，把 \(j\) 无视。把循环移位的式子拍上去：
\[\sum _{i = 0} ^{N - 1} a_ib_{(i + k) \bmod n} \]把 \(b\) 复制一遍把 \(\bmod\) 去掉。
\[\sum _{i = 0} ^{N - 1} a_ib_{i + k} \]把 \(a\) 序列翻转成 \(a'\)，用 \(a'_{N - i}\) 代替 \(a_i\)
\[\sum _{i = 0} ^{N - 1} a'_{N - i}b_{i + k} \]这玩意是个卷积，取 \(a'\) 数组和 \(b\) 数组卷积的 \(N + k\) 项系数就得到了这个式子的值。
套回去原式
\[c_k = \sum _{j = 0} ^5 2 ^ j \times [N + k] (a_j * b_j) \]最后对 \(c\) 数组求个 \(\max\) 就行了。
标签：le,我蝶,sum,ij,SError,2.0,移位,式子 From： https://www.cnblogs.com/AzusidNya/p/18233972