题解 P5300 【[GXOI/GZOI2019]与或和】

· · 题解

测试一开始看错题目敲了两小时，发现是个水题

目前是洛咕rk1 （开了O2的那种）

做法较为玄学，没有单调栈 因为不会

首先把 and 转化成 or ，这样我们只需要写半道题了

显然对于某一二进制位,我们需要求出此位 or 和为 1 的子矩阵个数。

枚举每一个位置作为右下角，记 s_i 为到当前行为止，当前位为 1 的数最后出现时的所在行。那么通过画图可知，这一位作为右下角的贡献就是以当前列作为右端点作后缀 Max ，再把后缀 Max 加起来的和。

因为后缀 Max 是单调的，而且每次修改只有一种操作：把某个位置（此位为 1 ）改成最大值（当前行号）。那么对于每个位置记 Pre_i ，表示在他之前最后一个比他大的，可以发现每个位置后缀最大值和可以用这个 Pre 求出。考虑一次修改的影响，我们只要扫一遍，记下最后一个改成最大值的位置，再和当前位的 Pre 取最大就可以了。

时间效率 O(n^2log)

而且代码很短的就0.7k

#include<cstdio>
#define L long long
const L p=1e9+7,N=1002,u=(1ll<<31)-1;
L n,a[N][N],s[N],v[N],r[N],A,O;
inline L S(L k) {
    L c=0;for(L j=1;j<=n;j++) s[j]=r[j]=0;
    for(L i=1;i<=n;i++)
        for(L j=1,w=0;j<=n;j++) {
            if(a[i][j]>>k&1) s[j]=i,r[w=j]=0;
            else if(w>r[j]) r[j]=w;
            v[j]=v[r[j]]+s[j]*(j-r[j]);
            c+=v[j];if(c>=p) c-=p;
        }return c*(1ll<<k)%p;
}
int main() {
    scanf("%lld",&n);
    for(L i=1;i<=n;i++) for(L j=1;j<=n;j++)
        scanf("%lld",&a[i][j]);
    for(L i=0;i<=30;i++) if((O+=S(i))>=p) O-=p;
    for(L i=1;i<=n;i++) for(L j=1;j<=n;j++) {
        a[i][j]^=u;if((A+=i*j*u%p)>=p) A-=p;
    }
    for(L i=0;i<=30;i++) if((A-=S(i))<0) A+=p;
return printf("%lld %lld\n",A,O),0;}