Codeforces Problem 405C. Unusual Product

Codeforces Problem 405C. Unusual Product 题意：求特殊矩阵的值，将结果值模2。这样就只剩下斜对角线值的自乘相加的和，然后摸2。 当遇见1 或者 2 的时候 对相应的行和列进行翻转，翻转后却只影响对角线上的一个值，并将该值翻转，即将最终的和值翻转。 思路：根据题目意思写，很简单。用if 或者 switch 都能将题目写得很清晰。 反思：刚开始忽略了数组从零开始，后来又超时了，就是没有找翻转的最终影响，模拟了翻转的过程，所以超时了。 代码：

/* ****
* @Codeforces Problem 405C. Unusual Product
* @quthor:ckeling
* @date: 2014.3.26
* @tag:implementation, math
******/

#include <stdio.h>
#define MAXN 1005

int linear[MAXN][MAXN];

int main(){
    int num;
    int i, j;
    int q, h, index, a, b, c;
    scanf("%d", &num);
    for(i = 0; i < num; ++i)
        for(j = 0; j < num; ++j)
            scanf("%d", &linear[i][j]);   // store the Matrix
    scanf("%d", &q);    // the number of the queries
    h = 0;
    c = 0;
    for(i = 0; i < num; ++i)
        c += linear[i][i]*linear[i][i];
    c %= 2;

    while(h++ < q){
        scanf("%d", &index);  // line data
        switch(index){
            case 1:
                scanf("%d", &a);
                c = !c;
                break;
            case 2:
                scanf("%d", &b);
                c = !c;
                break;
            case 3:
                printf("%d", c);
                break;
        }
    }
    printf("\n");

    return 0;
}
           

参考：

406A - Unusual Product

Written as a formula, the problem asks to find the value of

Suppose that i ≠ j. Then the sum contains summands AijAji and AjiAij. Since the sum is taken modulo 2, these summands together give 0 to the sum. It follows that the expression is always equal to the sum of the diagonal bits:

Now, each query of type 1 and 2 flips the value of exactly one bit on the diagonal. Thus we can calculate the unusual product of the original matrix, and flip its value after each query of type 1 and 2.

Solution complexity: O(n + q), if we don't take the reading of the input into account... :)