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... :)