ABC128 - C問題が解けない - irisuinwl’s diary

最近AtCoderに挑戦中。直近ではABC128に出たけど、ナイーブに全探索するって発想が出なかったので30分考えて匙投げてしまった（圧倒的に経験値が足りない

ABC128のC問題が面白かったので紹介する。回答を見ると $\mathbb{F}_2$ 上の連立方程式で解けるということなので解こうとしてるが2つWAになってしまって解けない…

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

#define MAX_INT 11

#define sum_f2(a,b) (a+b)%2

void debug_print_matrix(int matrix[MAX_INT][MAX_INT], int M, int N){
    printf("debug_print_matrix: \r\n");
    for(int i=0; i<M ;i++){
        for(int j=0; j<N ;j++){
            printf("%d ", matrix[i][j]);
        }
        printf("\r\n");
    }
}

// matrix method
void add_c_row(int matrix[MAX_INT][MAX_INT], int p, int q, int c, int N){
    // matrix[q][:] = matrix[p][:]*c+matrix[q][:]
    for (int i=0 ; i < N; i++){
        matrix[q][i] = sum_f2(matrix[q][i], matrix[p][i]*c);
    }
}

void exchange_row(int matrix[MAX_INT][MAX_INT], int p, int q, int N){
    int temp;
    for (int i=0 ; i < N; i++){
        temp = matrix[q][i];
        matrix[q][i] = matrix[p][i];
        matrix[p][i] = temp;
    }
}

void exchange_col(int matrix[MAX_INT][MAX_INT], int p, int q, int M){
    int temp;
    for (int i=0 ; i < M; i++){
        temp = matrix[i][q];
        matrix[i][q] = matrix[i][p];
        matrix[i][p] = temp;
    }
}

int get_rank(int matrix[MAX_INT][MAX_INT], int M, int N, bool hom){
    // gauss eliminationでrankを求める
    int ret = 0;
    int matrix_temp[MAX_INT][MAX_INT];
    for (int i = 0; i < M; i++){
        for (int j = 0; j < N; j++){
            matrix_temp[i][j] = matrix[i][j];
        }
    }
    int pivot = 0;
    // if (hom) N-=1;
    for (int i = 0; i < N && pivot < M; i++){
        if (matrix_temp[pivot][i] == 0){
            // 対角成分が0ならば行を交換する。
            int ex = -1;
            for (int j = pivot; j < M; j++){
                if (matrix_temp[j][i] != 0){
                    ex = j;
                    break;
                }
            }
            if (ex == -1) {
                continue;
            }
            exchange_row(matrix_temp, pivot, ex, N);
        }
        for (int j = pivot+1; j < M; j++){
            if (matrix_temp[j][i] == 1){
                add_c_row(matrix_temp, pivot, j, 1, N);
            }
        }
        // debug_print_matrix(matrix_temp, M, N);
        ret++;
        pivot++;
        
    }
    // debug_print_matrix(matrix_temp, M, N);
    return ret;
}

int main(){
    int N,M;
    int matrix[MAX_INT][MAX_INT]={0};
    int ret = -1;

    scanf("%d %d", &N, &M);

    int k;
    int s;
    for(int i = 0; i < M; i++){
        scanf("%d", &k);
        for(int j = 0; j < k; j++){
            scanf("%d", &s);
            // printf("debug: %d\r\n", s);
            matrix[i][s-1] = 1;
        }
    }
    
    for (int i=0; i < M; i++){
        scanf("%d", &(matrix[i][N]));
    }
    // debug_print_matrix(matrix, M, N);
    // debug_print_matrix(matrix, M, N+1);
    int rank = get_rank(matrix, M, N, false);
    if (M > N){
        int homo_rank = get_rank(matrix, M, N+1, true);
        // printf("debug: rank = %d\r\n", rank);
        // printf("debug: hrank = %d\r\n", homo_rank);
        if(homo_rank != rank)
        {
            printf("0\r\n");
            return 0;
        }
    }
    int dimker = N-rank;
    ret = (dimker == 0)? 1 : pow(2, dimker);
    printf("%d\r\n", ret);
    fflush(stdout);

    return 0;
}

理論的補足をすると、任意のスカラー体における線形空間での連立方程式の解について考える。（斎藤正彦の線形代数2.5の議論は体の性質しか使ってないので $\mathbb{F}_2$ としても成立する。）

連立方程式の解は線形変換 $f(x)=Ax+b$ における $ker f$ を考えればいい。

ここで、斉次化された方程式 $f(x)=\tilde{A}\tilde{x}$ を考えたら $rank A = rank \tilde{A}$ であれば、 $x _ 0 \in ker \tilde{A}$ について $ker A = \langle x _ 0 + Base(ker A) \rangle$ である。よって、線形多様体 $V(f)$ の解の個数は