題解

有個重要的觀察，就是 xor 後的數值一定會落在 $[0, 1024)$ 之間！

DP

對於每一個 row $r_i$，對於 $[0, 1024)$ 每個數值，如果我們可以利用 $r_0$ 到 $r_{i-1}$ xor 出來的話，我們記錄下我們的選擇。

Enumeration

對於每一個 row 我們都選第一個數字來 xor。如果結果不是 0，就得到解了; 如果結果是零，我們在任何一個 row 可以找一個與該 row 第一個數字不同的數字來替換的話，也得解，否則無解。

替換可以 work 的原因是：已知 $x_0\ xor\ x_1\ xor\ …\ x_n = 0$，你拿任一個 $x_i$ 出來，用一個不同的數字去換，必可以得到 $\neq 0$ 的結果。

AC Code

Using DP

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    // 500 * 500 * 1024 = 25 * 10^7 = 2.5 * 10^8
    vector<int> ans[1024]; 
    for (int i = 0; i < n; i++) {
        vector<int> newAns[1024];
        for (int j = 0; j < m; j++) {
            int num;
            scanf("%d", &num);

            if (i == 0) {
                if (newAns[num].size() == 0)
                    newAns[num].push_back(j);
            } else {
                for (int k = 0; k < 1024; k++) {
                    if (ans[k].size() > 0 && newAns[num ^ k].size() == 0) { 
                        // this optimization is a must 
                        // vector is slow 
                        vector<int> tmp(ans[k]);
                        tmp.push_back(j);
                        newAns[num ^ k] = tmp;
                    }
                }
            }
        }

        for (int j = 0; j < 1024; j++)
            ans[j] = newAns[j];
    }

    for (int i = 1; i < 1024; i++) {
        if (ans[i].size() > 0) {
            // print ans
            printf("TAK\n");
            for (auto j : ans[i])
                printf("%d ", j + 1);
            return 0;
        }
    }

    printf("NIE\n");

    return 0;
}

Using enumeration + observation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    int ans = 0;
    int selection[n] = {0};
    int inp[n][m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &inp[i][j]);
        }
        ans ^= inp[i][0];
    }

    if (ans == 0) {
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < m; j++) {
                // find diff
                if (inp[i][j] != inp[i][0]) {
                    selection[i] = j;
                    ans ^= inp[i][0];
                    ans ^= inp[i][j];
                    goto done;
                }
            }
            continue;
done:
            break;
        }
    }

    if (ans != 0) {
        printf("TAK\n");
        for (int i = 0; i < n; i++)
            printf("%d ", selection[i] + 1);
    } else {
        printf("NIE\n");
    }
}