Битовые операции. Mumatrix

@Dennis Ritchie · Регистрация: 27.07.2014

Студворк — интернет-сервис помощи студентам

Mumatrix

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 3 секунды

Ограничение по памяти: 256 мегабайта

Дана бинарная матрица. Возвести ее в квадрат по модулю 2.

Формат входных данных

Во входном файле число n $https://www.cyberforum.ru/cgi-bin/latex.cgi?(1 \leq n \leq 4000)$ . Далее n строк. В каждой n символов. Каждый — или 0, или 1.

Формат выходных данных

В выходном одно число — количество удиниц в матрице-квадрате-исходной.

Пример

Стандартный ввод
3
011
100
101
-------------------------
Стандартный вывод
5

P.S. Задачу нужно решить с помощью битовых операций (например, & и т. д.), иначе программа превысит лимит времени в тестирующей системе. Если никто не знает, как это сделать, то напишите, пожалуйста, программу без применения битовых операций.

@SlavaSSU · 20.10.2014, 00:36

не отправляется сообщение у меня(

только сслыку скину.

но я не уверен что это зайдет.

http://pastebin.com/9AgzU5WJ

@_Ivana · 20.10.2014, 00:40

Имхо, если не копать глубокие математические методы а считать честно в лоб, то вижу 2 сложности:
1) быстрый загон данных из файла в массив битовых строк исходной и особенно транспонированной матрицы, можно брать по 64 бита поле, если размер не кратен 64 - добивать матрицу справа/снизу нулями - результат не должен измениться. Потом это все эндится построчно во всех сочетаниях, и остается только:
2) задача быстрого выяснения - четное или нечетное количество единиц в 64-битовом поле. Пара минут поиска в инете дала достаточное количество ссылок, где народ реализует это красиво, умно и элегантно - без глупостей типа сдвига каждого битика в цикле.
Если 1) хорошо решить, то 2) не должно доставить проблем. но подумать и поискать информацию немножко придется конечно.

@Dennis Ritchie · 20.10.2014, 00:52 **[ТС]**

Сообщение от SlavaSSU

но я не уверен что это зайдет.

Точно не зайдёт:

Time Limit, TestN=18

@SlavaSSU · 20.10.2014, 01:00

Dennis Ritchie, а так?

C++ (Qt)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define X first
#define Y second
#define sqr(x) (x) * (x)
#define y1 __y1
#define endl '\n'
#define int unsigned int
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld PI = (ld)(3.1415926535897932384626433832795);
 
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
 
bool in(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}
 
const int N = 5555;
 
int cntver[N], cnthor[N];
int addhor[N], addver[N];
int maskhor[N][(N / 32) + 32], maskver[N][(N / 32) + 32];
int cntbit[(1 << 8) + 8];
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cout << setprecision(12) << fixed;
    cerr << setprecision(10) << fixed;
    
    srand(int(time(NULL)));
 
    int n;
    scanf("%d", &n);
 
    for(int mask = 0; mask < (1 << 8) + 7; mask++)
    {
        int m = mask, cnt = 0;
        while(m)
        {
            cnt++;
            m = (m - 1) & m;
        }
 
        cntbit[mask] = cnt;
    }
 
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++)
        {
            int c = int(s[j] - '0');
            if(c == 1)
            {
                maskhor[i][j / 32] |= (1 << (j % 32));
                maskver[j][i / 32] |= (1 << (i % 32));
                cnthor[i]++;
                addhor[i] = 1 - addhor[i];
                cntver[j]++;
                addver[j] = 1 - addver[j];
            }
        }
    }
 
    const int mag = 255;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(cnthor[i] == 0)
            continue;
        bool all = (cnthor[i] == n);
 
        for(int j = 0; j < n; j++)
        {
            if(cntver[j] == 0)
            {
                continue;
            }
 
            if(cntver[j] == n)
            {
                ans += addhor[i];
                continue;
            }
 
            if(all)
            {
                ans += addver[j];
                continue;
            }
 
            int cur = 0;
 
            for(int k = 0; k < N / 32; k++)
            {
                int mask = maskhor[i][k] & maskver[j][k];
                while(mask)
                {
                    int lastbyte = mask & mag;
                    cur += cntbit[lastbyte];
                    mask >>= 8;
                }
            }
 
            ans += (cur & 1);
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

а потом еще и так?

C++ (Qt)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define X first
#define Y second
#define sqr(x) (x) * (x)
#define y1 __y1
#define endl '\n'
#define int unsigned int
 
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld PI = (ld)(3.1415926535897932384626433832795);
 
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
 
bool in(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}
 
const int N = 5555;
 
int cntver[N], cnthor[N];
int addhor[N], addver[N];
int maskhor[N][(N / 32) + 32], maskver[N][(N / 32) + 32];
int cntbit[(1 << 16) + 8];
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cout << setprecision(12) << fixed;
    cerr << setprecision(10) << fixed;
    
    srand(int(time(NULL)));
 
    int n;
    scanf("%d", &n);
 
    for(int mask = 0; mask < (1 << 16) + 7; mask++)
    {
        int m = mask, cnt = 0;
        while(m)
        {
            cnt++;
            m = (m - 1) & m;
        }
 
        cntbit[mask] = cnt;
    }
 
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++)
        {
            int c = int(s[j] - '0');
            if(c == 1)
            {
                maskhor[i][j / 32] |= (1 << (j % 32));
                maskver[j][i / 32] |= (1 << (i % 32));
                cnthor[i]++;
                addhor[i] = 1 - addhor[i];
                cntver[j]++;
                addver[j] = 1 - addver[j];
            }
        }
    }
 
    const int mag = (1 << 16) - 1;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(cnthor[i] == 0)
            continue;
        bool all = (cnthor[i] == n);
 
        for(int j = 0; j < n; j++)
        {
            if(cntver[j] == 0)
            {
                continue;
            }
 
            if(cntver[j] == n)
            {
                ans += addhor[i];
                continue;
            }
 
            if(all)
            {
                ans += addver[j];
                continue;
            }
 
            int cur = 0;
 
            for(int k = 0; k < N / 32; k++)
            {
                int mask = maskhor[i][k] & maskver[j][k];
                while(mask)
                {
                    int lastbyte = mask & mag;
                    cur += cntbit[lastbyte];
                    mask >>= 16;
                }
            }
 
            ans += (cur & 1);
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

@Dennis Ritchie · 20.10.2014, 01:03 **[ТС]**

Сообщение от SlavaSSU

Dennis Ritchie, а так?

И так не лезет...

@SlavaSSU · 20.10.2014, 01:05

Dennis Ritchie, второй вариант тоже?

@Dennis Ritchie · 20.10.2014, 01:06 **[ТС]**

Сообщение от SlavaSSU

а потом еще и так?

Так лучше. Уже до 21-го теста добралось решение:

Time Limit, TestN=21

@SlavaSSU · 20.10.2014, 01:17

Dennis Ritchie, давай теперь так

C++ (Qt)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define X first
#define Y second
#define sqr(x) (x) * (x)
#define y1 __y1
#define endl '\n'
#define int unsigned int
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld PI = (ld)(3.1415926535897932384626433832795);
 
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
 
bool in(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}
 
const int N = 5555;
 
int cntver[N], cnthor[N];
int addhor[N], addver[N];
uli maskhor[N][(N / 32) + 32], maskver[N][(N / 32) + 32];
int cntbit[(1 << 16) + 8];
int mods[N], divs[N];
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cout << setprecision(12) << fixed;
    cerr << setprecision(10) << fixed;
    
    srand(int(time(NULL)));
 
    for(int i = 0; i < N; i++)
        mods[i] = i % 64, divs[i] = i / 64;
    int n;
    scanf("%d", &n);
 
    for(int mask = 0; mask < (1 << 16) + 7; mask++)
    {
        int m = mask, cnt = 0;
        while(m)
        {
            cnt++;
            m = (m - 1) & m;
        }
 
        cntbit[mask] = cnt;
    }
 
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++)
        {
            int c = int(s[j] - '0');
            if(c == 1)
            {
                maskhor[i][divs[j]] |= (uli(1) << (mods[j]));
                maskver[j][divs[i]] |= (uli(1) << (mods[i]));
                cnthor[i]++;
                addhor[i] = 1 - addhor[i];
                cntver[j]++;
                addver[j] = 1 - addver[j];
            }
        }
    }
 
    const int mag = (1 << 16) - 1;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(cnthor[i] == 0)
            continue;
        bool all = (cnthor[i] == n);
 
        for(int j = 0; j < n; j++)
        {
            if(cntver[j] == 0)
            {
                continue;
            }
 
            if(cntver[j] == n)
            {
                ans += addhor[i];
                continue;
            }
 
            if(all)
            {
                ans += addver[j];
                continue;
            }
 
            int cur = 0;
 
            for(int k = 0; k < n / 64 + 1; k++)
            {
                uli mask = maskhor[i][k] & maskver[j][k];
                while(mask)
                {
                    int lastbyte = mask & mag;
                    cur += cntbit[lastbyte];
                    mask >>= 16;
                }
            }
 
            ans += (cur & 1);
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

@Dennis Ritchie · 20.10.2014, 01:20 **[ТС]**

Сообщение от SlavaSSU

Dennis Ritchie, давай теперь так

Результат такой же:

Time Limit, TestN=21

@SlavaSSU · 20.10.2014, 01:23

Dennis Ritchie, давай последний раз пошли.
И я иду спать)))

C++ (Qt)
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define X first
#define Y second
#define sqr(x) (x) * (x)
#define y1 __y1
#define endl '\n'
#define int unsigned int
 
typedef long long li;
typedef long double ld;
typedef unsigned long long uli;
typedef pair<int, int> pt;
 
const int INF = (int)(1e9);
const li INF64 = (li)(INF) * (li)(INF);
const ld eps = 1e-9;
const ld PI = (ld)(3.1415926535897932384626433832795);
 
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
 
bool in(int i, int j, int n, int m)
{
    return i >= 0 && i < n && j >= 0 && j < m;
}
 
const int N = 5555;
 
int cntver[N], cnthor[N];
int addhor[N], addver[N];
int maskhor[N][(N / 32) + 32], maskver[N][(N / 32) + 32];
int cntbit[(1 << 16) + 8];
int mods[N], divs[N];
 
int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    cout << setprecision(12) << fixed;
    cerr << setprecision(10) << fixed;
    
    srand(int(time(NULL)));
 
    for(int i = 0; i < N; i++)
        mods[i] = i % 32, divs[i] = i / 32;
    int n;
    scanf("%d", &n);
 
    for(int mask = 0; mask < (1 << 16) + 7; mask++)
    {
        int m = mask, cnt = 0;
        while(m)
        {
            cnt++;
            m = (m - 1) & m;
        }
 
        cntbit[mask] = cnt;
    }
 
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++)
        {
            int c = int(s[j] - '0');
            if(c == 1)
            {
                maskhor[i][divs[j]] |= (int(1) << (mods[j]));
                maskver[j][divs[i]] |= (int(1) << (mods[i]));
                cnthor[i]++;
                addhor[i] = 1 - addhor[i];
                cntver[j]++;
                addver[j] = 1 - addver[j];
            }
        }
    }
 
    const int mag = (1 << 16) - 1;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(cnthor[i] == 0)
            continue;
 
        for(int j = 0; j < n; j++)
        {
            int cur = 0;
 
            for(int k = 0; k < n / 32 + 1; k++)
            {
                int mask = maskhor[i][k] & maskver[j][k];
                while(mask)
                {
                    int lastbyte = mask & mag;
                    cur += cntbit[lastbyte];
                    mask >>= 16;
                }
            }
 
            ans += (cur & 1);
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

@Dennis Ritchie · 20.10.2014, 01:25 **[ТС]**

Сообщение от SlavaSSU

Dennis Ritchie, давай последний раз пошли.

Хуже:

Time Limit, TestN=18

@SlavaSSU · 20.10.2014, 01:26

Dennis Ritchie, хотя щас еще 1 идейка есть. жди

хотя не она еще дольше будет, чет тупанул. ладно я мб спрошу у знакомых мб они знают.

@Dennis Ritchie · 20.10.2014, 17:26 **[ТС]**

А что делают команды:
#ifdef _DEBUG и #endif
Кстати, эти две строки можно не писать, ведь в этой задаче стандартный ввод-вывод:

C++
1
2
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

Добавлено через 6 минут

Сообщение от SlavaSSU

ладно я мб спрошу у знакомых мб они знают.

Хорошо. Спасибо за коды.

Добавлено через 15 часов 50 минут
Можно протестировать решение на скорость здесь:
МюМатрица

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	20.10.2014, 00:36
	не отправляется сообщение у меня( только сслыку скину. но я не уверен что это зайдет. http://pastebin.com/9AgzU5WJ 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	20.10.2014, 00:40
	Имхо, если не копать глубокие математические методы а считать честно в лоб, то вижу 2 сложности: 1) быстрый загон данных из файла в массив битовых строк исходной и особенно транспонированной матрицы, можно брать по 64 бита поле, если размер не кратен 64 - добивать матрицу справа/снизу нулями - результат не должен измениться. Потом это все эндится построчно во всех сочетаниях, и остается только: 2) задача быстрого выяснения - четное или нечетное количество единиц в 64-битовом поле. Пара минут поиска в инете дала достаточное количество ссылок, где народ реализует это красиво, умно и элегантно - без глупостей типа сдвига каждого битика в цикле. Если 1) хорошо решить, то 2) не должно доставить проблем. но подумать и поискать информацию немножко придется конечно. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	20.10.2014, 01:05
	Dennis Ritchie, второй вариант тоже? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	20.10.2014, 01:26
	Dennis Ritchie, хотя щас еще 1 идейка есть. жди хотя не она еще дольше будет, чет тупанул. ладно я мб спрошу у знакомых мб они знают. 0