Codeforces 400C 矩阵乘法数学规律

今天下午Virtual了一套最近的CF题，第三题给TLE了，就跑过去上课了。

这题给定一个由二进制表示的矩阵，当询问3的时候，求矩阵的值，矩阵的值是所有第i行乘以第i列的值的总和，然后还有1 b是翻转b行的数字 2 b是翻转b列的数字

一开始没怎么考虑复杂度，就直接想暴力过，觉得只要把翻转先暂存，最后有询问3的时候再pushdown再计算一下结果。。。简直不经大脑思考，有10^6询问，我这样做，如果询问全部是3，那光是计算矩阵10^6次就能达到12次方的复杂度。。。真是一点都不考虑。。。

后来在课上想了点方法，觉得把每一行和列的翻转都预处理一下，以及先把原始结果预处理出来，然后遇到翻转就跟之前的状态比一下看看要不要翻转结果的值。、。。遇到3就可以直接输出了，这样做还是WA了。。。

结果后来搜题解，发现，这个题目真的是个规律水题啊啊啊。。。很明显，n*n的矩阵如果是按i行与i列相乘的和作为结果的话，那么非对角线的元素都会与对称位相乘，并且还会加两次，同一个二进制值相加两次，那不就相当于没加，也就是说只有对角线的元素对结果有影响。。。。

想到这里真是要哭了，那不就很简单的一题目，先按位跟对角线的值异或得到初始结果，然后底下但凡有翻转操作，就把结果翻转（因为每次行或者列的翻转必定造成对角线某个元素翻转，也就直接造成结果翻转）。。然后遇到3直接输出结果即可啦

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int mat[][];

//int row[1010],col[1010]

int n,q;

//int change[1010][2][2];

//int pr[1010],pc[1010];

//void putdown()

//{

//    for (int i=1;i<=n;i++)

//    {

//        if (row[i])

//        {

//            for (int j=1;j<=n;j++)

//            {

//                mat[i][j]^=1;

//            }

//            row[i]=0;

//        }

//        if (col[i])

//        {

//            for (int j=1;j<=n;j++)

//            {

//                mat[j][i]^=1;

//            }

//            col[i]=0;

//        }

//    }

//}

//int counts()

//{

//    int ans=0;

//    for (int i=1;i<=n;i++)

//    {

//       int t=0;

//       for (int j=1;j<=n;j++)

//       {

//           int tmp=mat[i][j]*mat[j][i];

//           ans+=tmp;

//           t+=tmp;

//           //change[i][0][0]=tmp;

//       }

//       change[i][0][0]=t%2;

//    }

//    ans%=2;

//    return ans;

//

//}

//void init()

//{

//    for (int i=1;i<=n;i++)

//    {

//        int t1,t2,t3;

//        t1=t2=t3=0;

//        for (int j=1;j<=n;j++)

//        {

//

//            if (j==1)

//            {

//                t1+=(1-mat[i][j])*(1-mat[j][i]);

//                t2+=(1-mat[i][j])*(1-mat[j][i]);

//                t3+=(1-mat[i][j])*(1-mat[j][i]);

//            }

//            else

//            {

//                t1+=(1-mat[i][j])*mat[j][i];

//            t2+=mat[i][j]*(1-mat[j][i]);

//            t3+=(1-mat[i][j])*(1-mat[j][i]);

//            }

//        }

//        change[i][1][0]=t1%2;

//        //change[i][1][0]^=change[i][0][0];

//

//        change[i][0][1]=t2%2;

//        //change[i][0][1]^=change[i][0][0];

//

//        change[i][1][1]=t3%2;

//        //change[i][1][1]^=change[i][0][0];

//        //cout<<change[i][1][0]<<" "

//    }

//}

int main()

{

    int a,b;

   // freopen("CF_238.txt","w",stdout);

    while (scanf("%d",&n)!=EOF)

    {

        for (int i=;i<=n;i++)

        {

            for (int j=;j<=n;j++)

            {

                scanf("%d",&mat[i][j]);

            }

            //pr[i]=pc[i]=0;

        }

        int ans=;

        for (int i=;i<=n;i++)

           ans=ans^mat[i][i];

        //init();

        //int ans=counts();

        scanf("%d",&q);

        for (int i=;i<q;i++)

        {

            scanf("%d",&a);

            if (a<)

            {

                scanf("%d",&b);

                ans^=;

            }

            else

            {

                //putdown();

                //counts();

                printf("%d",ans);

            }

        }

        printf("\n");

    }

}

巴特西

Codeforces 400C 矩阵乘法数学规律

最新文章

热门文章

巴特西

Codeforces 400C 矩阵乘法 数学规律

最新文章

热门文章

Codeforces 400C 矩阵乘法数学规律