欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

第一次codeforces竞技结束 #238 Div 2

程序员文章站 2022-05-15 22:18:27
...

Little Chris is a huge fan of linear algebra. This time he has been given a homework about the unusual square of a square matrix. The dot product of two integer number vectors x and y of size n is the sum of the products of the correspondi

Little Chris is a huge fan of linear algebra. This time he has been given a homework about the unusual square of a square matrix.

The dot product of two integer number vectors x and y of size n is the sum of the products of the corresponding components of the vectors. Theunusual square of an n?×?n square matrix A is defined as the sum of n dot products. The i-th of them is the dot product of the i-th row vector and the i-th column vector in the matrix A.

Fortunately for Chris, he has to work only in GF(2)! This means that all operations (addition, multiplication) are calculated modulo 2. In fact, the matrix A is binary: each element of A is either 0 or 1. For example, consider the following matrix A:

第一次codeforces竞技结束 #238 Div 2

The unusual square of A is equal to (1·1?+?1·0?+?1·1)?+?(0·1?+?1·1?+?1·0)?+?(1·1?+?0·1?+?0·0)?=?0?+?1?+?1?=?0.

However, there is much more to the homework. Chris has to process q queries; each query can be one of the following:

  1. given a row index i, flip all the values in the i-th row in A;
  2. given a column index i, flip all the values in the i-th column in A;
  3. find the unusual square of A.

To flip a bit value w means to change it to 1?-?w, i.e., 1 changes to 0 and 0 changes to 1.

Given the initial matrix A, output the answers for each query of the third type! Can you solve Chris's homework?