『Codeforces 1186E 』Vus the Cossack and a Field (性质+大力讨论)

朱雀 2023-06-05 11:26 72阅读 0赞

# Description #

给出一个$n\\times m$的$01$矩阵$A$。

记矩阵$X$每一个元素取反以后的矩阵为$X'$，（每一个cell 都01倒置）

定义对$n \\times m$的矩阵$A$进行一次变幻操作，变幻后矩阵的大小是$2n \\times 2m$的。

具体来说，我们会把$A$复制一份到$A$的右下方，计算$A'$并放置在$A$的正右方和正下方。

设连续操作$n$的结果是$f^n(A)$ 即 $f^n(A) = \\left\\\{\\begin\{matrix\} f(f^\{n-1\}(A)) & (n\\geq 2)\\\\ \\begin\{Bmatrix\} A & A' \\\\ A' & A \\end\{Bmatrix\} & (n=1)\\\\A & (n = 0)\\end\{matrix\}\\right.$

设矩阵$L = f^\{\\infty\} (A)$ ，给出$Q$个询问，$x1,y1,x2,y2$，求出$L$中子矩阵的和。

对于$100\\%$的数据满足$1 \\leq n,m \\leq 10^3 , 1 \\leq Q \\leq 10^6 , 1 \\leq x1\\leq x2 \\leq 10^9 , 1 \\leq y1\\leq y2 \\leq 10^9$

# Idea & Solution #

我们不妨对于每个矩阵整体考虑。设没有进行翻转运算的矩阵为$0$，否则为$1$

必然是长这样的：$\\begin\{matrix\} 0 & 1 & 1& 0 & 1 & 0 & 0 & 1& ...\\\\ 1 & 0 & 0 & 1 & 0 &1 & 1 & 0 &...\\\\ 1 & 0 & 0 & 1 & 0 &1 & 1 & 0 & ...\\\\ 0 & 1 & 1& 0 & 1 & 0 & 0 & 1& ... \\\\ &&&&...\\end\{matrix\}$

我们会显然的发现第一个数字为$0$的序列都相同，第一个数字为$1$的序列都相同。

而两个序列恰好取反，于是我们可以尝试寻找第一行的性质。

如果我们从$0$开始编号，那么起始点就是$0$，其值为$0$.

对于第1行的第$i$个数字,必然是某一次扩展后产生的，我们会发现，一次扩展会对第一行的宽度$\\times 2$

所以，第$i$个数字是$01$是和$Highestbit(i)$相反的，所以我们可以归纳一下发现，对于第$1$行第$i$个元素如果二进制上的$1$的个数为偶数那么就是$0$否则就是$1$.

同时我们会发现纵向和横向的情况一模一样，所以可以进一步推论，$countbit(x) + countbit(y) $为偶数那么就是$0$否则就是$1$.

我们可能会发现，对于二维前缀和上的一个矩阵，$0$的个数和$1$的个数大致相等，可以分$x , y$坐标的奇偶性讨论$4$种可能即可计算。

最后使用二维前缀和求子矩阵和。

复杂度是$O(nm + T)$

# include<bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=1005;
    int s0[N][N],s1[N][N],a[N][N],b[N][N];
    int n,m,q;
    int count(int x) { int ret=0;while(x){
        if(x&1)ret++;x>>=1;}return ret;}
    pair<int,int> find(int x,int y) { return make_pair((x-1)/n,(y-1)/m);}
    int check(int x,int y) { return (count(x)+count(y))&1;}
    inline int read()
    {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    void write(int x)
    {
        if (x>9) write(x/10);
        putchar('0'+x%10);
    }
    int solve(int x,int y)
    {
        if (x<=0 || y<=0) return 0;
        pair<int,int>tmp=find(x,y); int cx = tmp.first, cy = tmp.second;
        if ((cx&1) && (cy&1)) {
            int ret = ((cx*cy-1)>>1)*n*m,h=x-cx*n,w=y-cy*m;
            ret=ret+h*((cy-1)>>1)*m+w*((cx-1)>>1)*n;
            if (check(cx,cy)==0) ret+=s0[h][w]; else ret+=s1[h][w];
            if (cx>=1 && cy>=1) { if (check(cx-1,cy-1)==0) ret+=s0[n][m]; else ret+=s1[n][m]; }
            if (cx>=1) { if (check(cx-1,cy)==0) ret+=s0[n][w]; else ret+=s1[n][w]; }
            if (cy>=1) { if (check(cx,cy-1)==0) ret+=s0[h][m]; else ret+=s1[h][m]; }
            return ret;
        } else if ((cx&1) && !(cy&1)) {
            int ret = (cx*cy>>1)*n*m,h=x-cx*n,w=y-cy*m;
            ret=ret+h*(cy>>1)*m+w*((cx-1)>>1)*n;
            if (check(cx,cy)==0) ret+=s0[h][w]; else ret+=s1[h][w];
            if (cx>=1) { if (check(cx-1,cy)==0) ret+=s0[n][w]; else ret+=s1[n][w]; }
            return ret;
        } else if (!(cx&1) && (cy&1)) {
            int ret = (cx*cy>>1)*n*m,h=x-cx*n,w=y-cy*m;
            ret=ret+h*((cy-1)>>1)*m+w*(cx>>1)*n;
            if (check(cx,cy)==0) ret+=s0[h][w]; else ret+=s1[h][w];
            if (cy>=1) { if (check(cx,cy-1)==0) ret+=s0[h][m]; else ret+=s1[h][m]; }
            return ret;
        } else if (!(cx&1) && !(cy&1)) {
            int ret = (cx*cy>>1)*n*m,h=x-cx*n,w=y-cy*m;
            ret=ret+h*(cy>>1)*m+w*(cx>>1)*n;
            if (check(cx,cy)==0) ret+=s0[h][w]; else ret+=s1[h][w];
            return ret;
        }
    }
    signed main()
    {
        n=read();m=read();q=read();
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                char c=0; while (c!='0'&&c!='1') c=getchar();
                a[i][j]=(c=='1'); b[i][j]=1-a[i][j];
            }
        }
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++)
          s0[i][j]=s0[i-1][j]+s0[i][j-1]-s0[i-1][j-1]+a[i][j],
          s1[i][j]=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1]+b[i][j];
        while (q--) {
            int x1=read(),y1=read(),x2=read(),y2=read(); 
            int ans = solve(x2,y2)-solve(x2,y1-1)-solve(x1-1,y2)+solve(x1-1,y1-1);
            write(ans); putchar('\n');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/ljc20020730/p/11431852.html